Law of Commutation

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Description

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$).

Input

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$.

Output

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

Sample Input

2 3 2 2

Sample Output

1 2

Hint

liuyiding

Source

2017ACM/ICPC广西邀请赛-重现赛(感谢广西大学)

提交代码