Description

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

Mr.I creates a sequence $b_x=ax(modP)$ of length P−1 ,where $1≤x≤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$.

Format

Input

The first line contains an integer T $(T≤10^5)$ . Then T test cases follow.

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

Output

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

Samples

4
2 7
3 7
4 7
5 7

0
1
0
1