Hide
Problem A
Happy Equation
Little Sub has just received the following equation as his birthday gift.
\[ a^ x \equiv x^ a (\text {mod } 2^ p) \]Given the value of $a$, please help Little Sub count the number of $x$ ($1 \le x \le 2^ p$) which satisfies the equation.
Input
There are multiple test cases. The first line of the input contains an integer $T$ (at most $1000$), indicating the number of test cases. For each test case:
The first and only line contains two integers $a$ and $p$ ($1 \leq a \leq 10^9$, $1 \leq p \leq 30$).
Output
For each test case output one line containing one integer, indicating the answer.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 6 12 8 16 |
1023 16383 |