Given integers , , and , calculate the value modulo .

Input Format
The first line contains the number of test cases .
Each of the next lines contains four space-separated integers , , and .

Output Format
For each test case output one integer: the value of the sum.

Note In this problem we take

Constraints





The sum of all in one test file doesn't exceed 1000

Sample input

5
3 1 1 100
3 0 1 100
3 1 0 100
44 44 4 444
77 7 47 747

Sample Output

6
4
0
288
288

Explanation