#P14052. [SDCPC 2019] Happy Equation

[SDCPC 2019] Happy Equation

题目描述

Little Sub has just received an equation, which is shown below, as his birthday gift. axxa(mod2p)a^x \equiv x^a \pmod {2^p} Given the value of aa, please help Little Sub count the number of xx (1x2p1 \le x \le 2^p) which satisfies the equation.

输入格式

There are multiple test cases. The first line of the input contains an integer TT (about 10001000), indicating the number of test cases. For each test case:

The first and only line contains two integers aa and pp (1a1091 \leq a \leq 10^9, 1p301 \leq p \leq 30).

输出格式

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

2
6 12
8 16
1023
16383