Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4123
Happy Equation

Time Limit: 1 Second      Memory Limit: 65536 KB

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.

Sample Input

2
6 12
8 16

Sample Output

1023
16383

Author: CHEN, Jingbang
Source: The 10th Shandong Provincial Collegiate Programming Contest
Submit    Status