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.

Video approach to solve this question: here

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$