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 \leq t \leq 10^5$, the number of test cases.

Each test case consists of two lines. First line consist of an integer $3 \leq n \leq 2^{63}-1$. The second line consists of an integer $1 \leq a \leq \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