G. Hard Equation
time limit per test
10 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Consider the following equation

Given a, b and m, your task is to find a value x that satisfy the equation for the given values. Can you?

Input

The first line contains an integer T (1 ≤ T ≤ 500), in which T is the number of test cases.

Each test case consists of a line containing three integers a, b and m (0 ≤ a, b < m ≤ 109).

Output

For each test case, print a single line containing an integer x (0 ≤ x ≤ 1017) that satisfy the equation , for the given a, b and m.

If there are multiple solutions, print any of them. It is guaranteed that an answer always exist for the given input.

Example
Input
3
3 9 11
2 3 5
2 1 5
Output
2
3
4