6970：I love permutation

Mr.I has a positive integer a and an odd prime number P, satisfying a<P.

Mr.I creates a sequence $b_x=ax(mod P)$ of length $P-1$ ,where$1\leq x \leq P-1$。

Now Mr.I wants to know how many reversed pairs there are in this sequence.

Since the answer may be very large, you only need to output the value of the answer pair modulo $2$.

The definition of a reverse pair is a two-tuple $(i, j)$ that satisfies $i<j$ and $b_i>b_j$.

The first line contains an integer $T(T\leq {10}^{5})$ . Then $T$ test cases follow.

Each test case contains two integers $a,P(1\leq a < P \leq {10}^{18})$.

For each test case, output a single line contain the answer for the test case.