As we all know, operation ''+'' complies with the commutative law. That is, if we arbitrarily select two integers $a$ and $b$, $a + b$ always equals to $b + a$. However, as for exponentiation, such law may be wrong. In this problem, let us consider a modular exponentiation. Give an integer $m = 2^n$ and an integer $a$, count the number of integers $b$ in the range of $[1,m]$ which satisfy the equation $a^b \equiv b^a$ (mod $m$).

There are no more than $2500$ test cases.

Each test case contains two positive integers $n$ and a seperated by one space in a line.

For all test cases, you can assume that $n \leq 30, 1 \leq a \leq 10^9$.

For each test case, output an integer denoting the number of $b$.