Practice on Toph

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

Trivial Summation

By hasan169 · Limits 2s, 512 MB

The problem statement is so small. Give you four integers r, a, b, d. Find the summation of all numbers from 1 to r, those are divisible by a or b. Since the result can be very large, you have to print the result modulo d.
Mathematically, ( i=1∑r i ) % d [ if i % a == 0 or i % b == 0 ]

Input

At first gives you an integer T (T<=100000), is the number of test cases. Each test case contains four integers r, a, b, d (1 <= r, a, b, d <= 10^18).

Output

For every test case, print required result.

Sample

InputOutput
2
10 3 5 7 
15 7 14 7
5
0

Look, for test case 1. From 1 – 10, there are 5 numbers 3, 5, 6, 9, 10 those are divisible by 3 or 5. So (3+5+6+9+10) % 7 = 33 % 7 = 5.

Discussion

Statistics


32% Solution Ratio

AashiqEarliest, Jan '17

arnob_daFastest, 0.1s

AashiqLightest, 1.2 MB

white_negroShortest, 227B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.