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 ≤ 100000 ) . K dòng tiếp theo mỗi dòng gồm 2 số nguyên a , n ( 1 ≤ a , n ≤ 32767 ) .

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