2019 ICPC Asia Danang Regional Contest

Start

2019-12-05 16:20 AKST

2019 ICPC Asia Danang Regional Contest

End

2019-12-05 21:20 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -323 days 8:29:50

Time elapsed

5:00:00

Time remaining

0:00:00

Problem D
Dating time

/problems/datingtime/file/statement/en/img-0001.png
Photo by Phrontis, via Wikipedia.

Our two lovebirds, Banmuon and Henho want to go on a date. However, they are afraid that their friends or families may find out. Thus, they have decided to setup their dating time using the following secret methods:

  • Banmuon will send Henho a string with format h1:m1 h2:m2 alpha where h1:m1 and h2:m2 represent some time in $24$-hour format. $alpha$ is an integer between $0$ and $180$ and is divisible by $90$.

  • Their dating time will be some time between h1:m1 and h2:m2, where the two clock hands, hour and minute, forms an angle equals to $alpha$ degree.

However, there is a problem: their dating time may not be unique! Please help Banmuon and Henho figure out how many possible valid dating times there are.

Note

In this problem, we use a normal analog clock:

  • The minute hand rotates continuously. It takes $60$ minutes to make one complete rotation (from $12$ to $12$).

  • The hour hand rotates continuously. It takes $12$ hours to make one complete rotation (from $12$ to $12$).

Input

The first line of input contains a single integer $t$ $(1 \le t \le 100)$ — the number of test cases.

$t$ lines follow, each line has format: h1:m1 h2:m2 alpha $(0 \le h_1, h_2 \le 23, 0 \le m_1, m_2 \le 59, 0 \le alpha \le 180)$. $h_1$, $m_1$, $h_2$ and $m_2$ will have exactly two digits, with leading zero if they are less than $10$.

It is guaranteed that h1:m1 is less than or equal to h2:m2 and $alpha$ is divisible by $90$.

Output

For each test case, print the number of instants when the two clock hands form an angle equals to $alpha$ degrees, between h1:m1 and h2:m2, inclusive.

Explanation of Sample input

In the first test case, there are $22$ instants when the two clock hands form a $0$-degree angle. Below are the first $11$ instants.

  1. 00:00

  2. 01:05 and $\frac{5}{11}$ minute.

  3. 02:10 and $\frac{10}{11}$ minute.

  4. 03:16 and $\frac{4}{11}$ minute.

  5. 04:21 and $\frac{9}{11}$ minute.

  6. 05:27 and $\frac{3}{11}$ minute.

  7. 06:32 and $\frac{8}{11}$ minute.

  8. 07:38 and $\frac{2}{11}$ minute.

  9. 08:43 and $\frac{7}{11}$ minute.

  10. 09:49 and $\frac{1}{11}$ minute.

  11. 10:54 and $\frac{6}{11}$ minute.

Sample Input 1 Sample Output 1
3
00:00 23:59 0
00:00 23:59 90
18:00 18:01 180
22
44
1