Reference: AtCoder ABC186 E — Throne

There are ~N~ chairs arranged in a circle. One of the chairs is a throne.

Initially, Takahashi is sitting on the chair located ~S~ chairs clockwise from the throne.

In one move, he moves to the chair located ~K~ chairs clockwise from his current chair.

Find the number of moves required for Takahashi to sit on the throne for the first time.

If he can never reach the throne, print ~-1~.

You must answer ~T~ test cases.

Input

• The first line contains one integer ~T~.
• Each of the following ~T~ lines contains three integers: ~N~, ~S~, and ~K~.

Output

• For each test case, print the answer on a separate line.

Constraints

• ~1 \le T \le 100~
• ~2 \le N \le 10^9~
• ~1 \le S < N~
• ~1 \le K \le 10^9~

Example 1

Input:

4
10 4 3
1000 11 2
998244353 897581057 595591169
10000 6 14

Output:

2
-1
249561088
3571