Hide

Problem DDating time

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

CPU Time limit 1 second
Memory limit 1024 MB