Given three numbers x, y and z, Calculate (xy) % z.

Note: % is the modulo operator for finding remainder.

For example- if x, y and z are 3, 4 and 5 respectively:

(34) % 5 = 1

Input Format

The first line contains ‘T’ denoting the number of test cases.

The next ‘T’ line contains three numbers 'x', ‘y’, and ‘z’.

Output Format

T lines, each containing the result of (xy) % z.

Examples

Sample Input

2
5 2 5
3 3 2

Expected Output

0
1

Constraints

1 <= T <= 104
1 <= x, y <= 105
1 <= z <= 104