Trivial Summation

hasan169 Replay of Intra AUST Prog...
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.

Submit

Login to submit.

Statistics

31% Solution Ratio
AashiqEarliest, Jan '17
Yasir_ArafatFastest, 0.0s
AashiqLightest, 1.2 MB
SabbasachiSutradharShortest, 212B
Toph uses cookies. By continuing you agree to our Cookie Policy.