SOLVE
LATER
Given two integers N and M, help Monk find an integer X, such that \(X^2 \; \% \; M = N\) and \(0 \le X\). If there are multiple values of X print smallest one. If there is no possible value of X print 1.
Note: Make sure you handle integer overflow.
Input:
First line consists of a single integer T denoting the number of test cases.
Each test case consists of a single line containing two space separated integers denoting N and M.
Output:
For each test case print the required answer.
Constraints:
\(1 \le T \le 100\)
\(0 \le N \lt M \le 10^6\)
2 is the smallest positive integer such that \((2 \times 2) \; \% 5 = 4\)