Limits 1s, 512 MB

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 aa-th unit of time starting from 0, i.e. at times aa, 2a2a, 3a3a, 4a4a, ..., NaNa
  • F2 gets a chance to go out after every bb-th unit of time starting from 0, i.e. at times bb, 2b2b, 3b3b, 4b4b, ..., NbNb

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 cc-th unit of time starting from 0, i.e at times cc, 2c2c, 3c3c, 4c4c, ..., NcNc. So if there exists time unit t1at_1a, t2bt_2b and t3ct_3c such that t1a==t3ct_1a == t_3c then F1 can't go out and if t2b==t3ct_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][1, n]?

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


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

Each of the next TT lines will contain 4 positive integers nn (1n1091 ≤ n ≤ 10^9), aa, bb, cc (1a,b,c1061 ≤ a, b, c ≤ 10^6).


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


10 2 4 5
18 3 5 10
20 1 2 3

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.


Login to submit.


70% Solution Ratio
Riaz_BSMRSTUEarliest, May '20
arafraihan7Fastest, 0.0s
Riaz_BSMRSTULightest, 655 kB
mdvirusShortest, 206B
Toph uses cookies. By continuing you agree to our Cookie Policy.