Description

Little Sub has just received an equation, which is shown below, as his birthday gift. ax≡xa(mod 2p)ax≡xa(mod 2p) Given the value of aa, please help Little Sub count the number of xx (1≤x≤2p1≤x≤2p) which satisfies the equation.

Input

There are multiple test cases. The first line of the input contains an integer TT (about 1000), indicating the number of test cases. For each test case:
The first and only line contains two integers aa and pp (1≤a≤1091≤a≤109, 1≤p≤301≤p≤30).

Output

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

Sample Input

2
6 12
8 16

Sample Input

1023
16383

题目大意

题目意思不难理解就是输出1-2^p范围内满足式子ax≡xa(mod 2p)的x个数

解题思路

分a为奇偶考虑
a为奇数打表可以看出为1
a为偶数则x也为偶数a=2^m *k1，x=2ⁿ *k2
原式左边等于2^m*x *k1^k右边等于2^n*a *k2^a因为要对2^p取模所以也可以将m *k分情况讨论

1. m* x>=p此时原式左边对2^p取模为0，要使恒等式成立那么右边也要为0则n*a>=p于是就有x>=p/m（取上界）令x=p/m（取上界）。那么x的取值范围缩小到了[l，2^p]由于有关系x=2ⁿ*k2，那么只要求在该范围内符合x=2ⁿk2的取值数。n是可变的，那么我们取下界 na>=p ------> n>=p/a（取上界）令下界为v。那么这种情况符合式子的个数为 2^p/2^v-2^l/2^v+(2^l%2^v==0)（因为区间左边是闭区间）
2. m* x<p此时原式没有较好的判断方法，不过数据较小可以暴力

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll mod,w[35];
ll pow_(ll a,ll b)
{
    ll ans=1,v=a;
    while(b)
    {
        if(b&1)
            ans=(ans*v)%mod;
        v=(v*v)%mod;
        b>>=1;
    }
    return ans;
}
int main()
{
    w[0]=1;
    for(int i=1;i<32;++i)
        w[i]=w[i-1]<<1;
    ll a,p,t;
    cin>>t;
    while(t--)
    {
        cin>>a>>p;
        if(a&1)
        {
            cout<<1<<endl;
            continue;
        }
        ll b=a,m=0;
        mod=pow(2,p);
        while(!(b&1))
        {
            ++m;
            b>>=1;
        }
        ll l=(p%m)?p/m+1:p/m;
        ll v=(p%a)?p/a+1:p/a;
        ll ans=w[p]/w[v]-l/w[v]+(l%w[v]==0);
        for(ll x=1;x*m<p;++x)
        {
            if(pow_(a,x)==pow_(x,a))
                ++ans;
        }
        cout<<ans<<endl;
    }
}