Trivial Summation

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

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