Khóa nghịch đảo modulo

Bối cảnh và bài toán

Một hệ thống mã hóa tuyến tính dùng phép nhân modulo m. Để giải mã hệ số a, hệ thống cần tìm số x sao cho a*x ≡ 1 (mod m). Không phải mọi cặp (a,m) đều có một khóa nghịch đảo như vậy.

Bạn cần xử lý nhiều yêu cầu và trả về nghịch đảo chuẩn nhỏ nhất không âm khi nó tồn tại.

Yêu cầu

Với mỗi cặp (a,m), in nghịch đảo modulo của a theo m, tức số x duy nhất trong 0 <= x < m thỏa a*x ≡ 1 (mod m). Nếu không tồn tại, in -1.

Input

• Dòng 1: số nguyên q.
• q dòng tiếp theo: mỗi dòng chứa a m.

Output

Với mỗi truy vấn, in nghịch đảo modulo chuẩn hóa hoặc -1 nếu không tồn tại.

Ràng buộc

• 1 <= q <= 10^5
• 1 <= a < m <= 10^9

Chấm điểm

Ví dụ 1

Input

4
3 7
2 4
10 17
12 18

Output

5
-1
12
-1

Giải thích. 3*5=15 ≡1 (mod 7). Với 2,4 và 12,18, GCD lớn hơn 1 nên không có nghịch đảo.

Ví dụ 2

Input

2
1 9999
35 64

Output

1
11

Giải thích. 35*11=385 ≡1 (mod 64).

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.