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 ath unit of time starting from 0, i.e. at times a, 2a, 3a, 4a... Na

F2 gets a chance to go out after every bth 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 in the gate. The guard become active after every cth unit of time starting from 0, i.e at times c, 2c, 3c, 4c, ... Nc. So if there exists time unit t1a, t2b and t3c such that t1a == t3c then F1 can't go out and if t2b == t3c 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 human :D.

Input

The first line contains a positive integer T (1 ≤ T ≤ 105), the number of test case. Each of the next T lines will contain 4 positive integers n, a, b, c. NB:n, a, b, c is described in the statement. Read the statement carefully. 1 ≤ n ≤ 109 1 ≤ a, b, c ≤ 106

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.