大胆猜测，所有数的最大公约数一定很小：偶数时为 \(1\)，奇数时为 \(2\)。设两个正整数 \(n,m\) 且 \(n<m\)，最大公约数 \(\gcd(k^{2^n}+1,k^{2^m}+1)=d\)，则有 \(k^{2^n}\equiv k^{2^m} \equiv -1\pmod d,k^{2^{n+1}} \equiv (k^{2^{n+1}})^{\frac{2^m}{2^{n+1}}} \equiv k^{2^m} \equiv 1 \pmod d\)，故 \(-1 \equiv 1 \pmod d\)，即 \(d\) 只能为 \(1\) 或 \(2\)，当且仅当 \(k=1\) 时 \(d=2\)。
现在要求 \((k^{2^l}+1)(k^{2^{l+1}}+1)\cdots(k^{2^r}+1)\)。这个式子的意义可以理解为二进制上每一位选或不选，那么每一个 \(k\) 的幂一定恰好出现一次，则答案为 \(\dfrac{k^{2^{r+1}}-1}{k^{2^l}-1}\)。比如 \((k^1+1)(k^2+1)(k^4+1)=k^0+k^1+\cdots+k^7=\dfrac{k^8-1}{k-1}\)（\(l,r+1\) 的两个分式可以消去分子）。直接使用逆元计算即可。以下是特殊情况：
- 分母为 \(0\) 时，\(k^{2^l} \equiv 1 \pmod p\)，后面 \(k\) 的幂也是同样的结果，直接输出 \(2^{r-l+1}\) 即可。
- 使用费马小定理减小指数，注意此时模数为 \(p-1\)（\(p=2\) 时不符合使用条件，直接特判即可）。
- 如果 \(k\) 是奇数，最后再乘上 \(2^{r-l}\) 的逆元即可（乘多的部分）。
#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
int k,l,r,p,n;
int qp(int a,int b,int mod){a=(a%mod+mod)%mod;int c=1;while(b){if(b&1)c=c*a%mod;b>>=1;a=a*a%mod;}return c;
}
int calc(int x){if(k%p==0)return 0;n=qp(2,x+1,p-1);// cout<<n<<endl;return qp(k,n,p);
}
signed main(){int T;cin>>T;while(T--){cin>>k>>l>>r>>p;if(p==2){if(k%2)cout<<0<<'\n';else cout<<1<<'\n';continue;}if(calc(l-1)==1){if(k&1)cout<<qp(2,r-l+1,p)*qp(qp(2,r-l,p),p-2,p)%p<<'\n';else cout<<qp(2,r-l+1,p)<<'\n';continue;}if(k&1)cout<<((calc(r)-1)*qp((calc(l-1)-1),p-2,p)%p*qp(qp(2,r-l,p),p-2,p)%p+p)%p<<'\n';else cout<<((calc(r)-1)*qp((calc(l-1)-1),p-2,p)%p+p)%p<<'\n';}return 0;
}
)
)
