Description

Little Sub has just received an equation, which is shown below, as his birthday gift. $a^x \equiv x^a \pmod {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 Format

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 Format

For each test case output one line containing one integer, indicating the answer.

2
6 12
8 16

1023
16383