# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

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

*

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 **c ^{th}** unit of time starting from 0, i.e at times

There is a counter in the gate which counts the number of times a group of people go out passing through the gate.

Now the question is can you calculate the value of the counter for a given time segment

Please ignore the time needed to go from the hostel to the gate. Just imagine they are super human :D.

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

1 ≤ a, b, c ≤ 10

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

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. |

70% Solution Ratio

Riaz_BSMRSTUEarliest,

TurinhstuFastest, 0.1s

Riaz_BSMRSTULightest, 655 kB

mdvirusShortest, 206B

Login to submit