K. Happy Equation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Little Sub has just received an equation, which is shown below, 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$$$ (about $$$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.

Example
Input
2
6 12
8 16
Output
1023
16383