Giải bài trực tuyến

Tìm tất cả số các nguyên x thoả mãn (x*x) mod n = a mod n. Trong đó n là số nguyên tố và ước chung lớn nhất của a và n = 1, 0 ≤ x ≤ n – 1 .

Input

Dòng 1: số nguyên K là số bộ test ( 1 ≤ K ≤ 120000 ). K dòng tiếp theo mỗi dòng gồm 2 số nguyên a , n ( 1 ≤ a, n ≤ 1000000 ).

Output

Với mỗi test ghi ra tất cả các số nguyên x thoả mãn theo thứ tự tăng dần trên 1 dòng . Nếu không có số nguyên x nào thoả mãn thì ghi ra “Khong co”.

Example

Input:
5
4 17
3 7
2 7
14 31
10007 20011

Output:
2 15
Khong co
3 4
13 18
5382 14629