P405232 - GYM101853 G Hard Equation - SSOJ - 省实信息奥赛评测系统

Memory Limit：256 MB Time Limit：10 S

Judge Style：Text Compare Creator：

Submit：0 Solved：0

G. Hard Equationtime limit per test10 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Consider the following equation

$\text{[math]}$

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 ≤ 10⁹).

Output

For each test case, print a single line containing an integer x (0 ≤ x ≤ 10¹⁷) that satisfy the equation $\text{[math]}$ , 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.

ExampleInput

Output

2
3
4

405232: GYM101853 G Hard Equation