Your \(N\) friends are seated in a circle and are numbered from \(0\) to \(N-1\). Initially, you are sitting beside the \(A^{th}\) friend. After greeting one friend, you go clockwise to the \(B^{th}\) next friend, sit next to that person and greet your friend. You repeat this till you return to the \(A^{th}\) friend.

It is possible that you might not greet some friends. Your task is to determine the number of friends that you can greet before reaching back to \(A\).

Input format

• First line: \(T\) denoting the number of test cases
• Each of the next \(T\) lines: Three space-separated integers denoting the values of \(A\), \(B\), and \(N\) for that test case

Output format

For each test case, print the number of friends that you can greet before reaching back to \(A\).

Constraints

\(1 ≤ T ≤ 100000\\ 1 ≤ N ≤ 10^{15}\\ 0 ≤ B ≤ 10^{15}\\ 0 ≤ A < N\)