The Story of Two Friends

There are two friends F1 and F2 in a city. They both are student of FCB High School. Also, they reside in the same school hostel.

Every afternoon, they get out of the hostel to play in the school play ground.

They are so fond of playing that whenever they get the chance to go out they never miss it. They also follow a strange rule.

The rules are:

• F1 gets a chance to go out after every $a$-th unit of time starting from 0, i.e. at times $a$, $2a$, $3a$, $4a$, ..., $Na$
• F2 gets a chance to go out after every $b$-th unit of time starting from 0, i.e. at times $b$, $2b$, $3b$, $4b$, ..., $Nb$

But, there's a problem.

When F1 or F2 (or both) try to go out passing through the hostel gate, there is a guard at the gate. The guard become active after every $c$-th unit of time starting from 0, i.e at times $c$, $2c$, $3c$, $4c$, ..., $Nc$. So if there exists time unit $t_1a$, $t_2b$ and $t_3c$ such that $t_1a == t_3c$ then F1 can't go out and if $t_2b == t_3c$ then F2 can't go out because of the guard.

There is a counter in the gate which counts the number of times a group of people go out passing through the gate. Note, the counter consider one or more people a group if at a single moment of time unit they all go out together.

Now the question is can you calculate the value of the counter for a given time segment $[1, n]$?

Please ignore the time needed to go from the hostel to the gate. Just imagine they are super humans. 😀

Input

The first line contains a positive integer $T$ ($1 ≤ T ≤ 10^5$), the number of test case.

Each of the next $T$ lines will contain 4 positive integers $n$ ($1 ≤ n ≤ 10^9$), $a$, $b$, $c$ ($1 ≤ a, b, c ≤ 10^6$).

Output

Print $T$ lines of output, the value of the counter in the time segment $[1, n]$ for each dataset.

Sample

Input	Output
3 10 2 4 5 18 3 5 10 20 1 2 3	4 7 14
For case #1, n = 10, a = 2, b = 4, c = 5. F1 gets chance at times 2, 4, 6, 8, 10. F2 gets chance at times 4, 8. The guard becomes active at times 5, 10. Here, The guard can prevent F1 once at times 10. So the counter will increase only at 2, 4, 6, 8. Hence, the result is 4.