Scooby and all of his friends have gathered for a party. There are N friends present. Scooby is really happy to see all of his friends in one place and is excited to greet them.

All N friends are seated in a circle, and are numbered from 0 to N-1. Scooby is initially sitting beside the A^th friend. After greeting one friend, he goes clockwise to the B^th next friend, sits next to him and greets him. He repeats this till he returns to the A^th friend.

In his excitement, it is possible that Scooby misses out on greeting some friends. Your job is to find the number of friends (including A) that Scooby will have greeted before reaching back to A.

Input:

The first line contains T, the number of test cases.

Each of the next T lines contain three space-separated integers, the values of A, B and N for that test case.

Output:

For each test case, output the number of friends that Scooby will have greeted before reaching back to A.

Constraints:

1 ≤ T ≤ 100000

1 ≤ N ≤ 10¹⁵

0 ≤ B ≤ 10¹⁵

0 ≤ A < N