Problem B
Miller-Rabin Witness

Determine if an integer $a$ is a Miller-Rabin witness for an integer $n$.

Input

The first line contains a number $1\le t\le {10}^5$, the number of test cases.

Each test case consists of two lines. First line consist of an integer $3\le n\le 2^{63}-1$. The second line consists of an integer $1\le a\le min\{n-1,2^{31}-1\}$.

Output

For each test case, write a single line with $1$ if $a$ is a Miller-Rabin witness for $n$, or $0$ otherwise.

2
561
2
172947527
17

1
0