Đường đến ngai vàng

Trên vòng tròn $N$ vị trí, từ $S$ và mỗi bước tiến $K$ , hãy tìm số bước nhỏ nhất để tới vị trí $0$ . Sau $t$ bước, vị trí là ( $S + t \cdot K$ ) mod $N$ ; $t = 0$ cũng được xét.

Input

Dòng đầu chứa $T$ ; mỗi dòng sau chứa $N, S, K$ .

Output

Mỗi test in số bước nhỏ nhất hoặc $- 1$ .

Constraints

$1 \leq T \leq 100.$
$1 \leq N, K \leq 1 0^{9}; 0 \leq S < N .$

Scoring

Subtask $1$ ( $50%$ số điểm): các test từ $1$ đến $10$ , dùng miền dữ liệu nhỏ để có thể đối chiếu độc lập.
Subtask $2$ ( $50%$ số điểm): không có giới hạn bổ sung ngoài các ràng buộc đã nêu.

Example

Test 1

Input

Output

2
-1
0

Giải thích: Hai truy vấn đầu lần lượt cần $2$ bước và vô nghiệm; ở truy vấn cuối người chơi đã đứng tại vị trí $0$ nên đáp án là $0$ .

Lời giải tóm tắt

Ý tưởng: Cần tìm t≥0 nhỏ nhất sao cho S+t·K≡0 (mod N), tức K·t≡-S (mod N). Gọi g=gcd(K,N). Nếu g không chia S, đồng dư vô nghiệm và đáp án là -1.
Ý tưởng: Nếu có nghiệm, chia cả phương trình cho g. Euclid mở rộng tìm nghịch đảo của K/g modulo N/g; nhân với -S/g rồi chuẩn hóa về [0,N/g-1] sẽ cho t nhỏ nhất không âm.
Ý tưởng: Độ phức tạp mỗi test là O(log N).