看到异或和，大概就是对二进制下每一位分开操作了。

题意大概就是比$k$小的$t=i\operatorname{xor}j$ 的贡献不要了，剩下的贡献减去$k$*剩下的数量。

所以把两个部分分开来看吧。

第一部分其实可以关注比$k$小，如何实现比$k$小？

若在二进制的高位上，$t$已经比$k$小了，那以后的低位无论怎么搞，也不可能大于$k$。

第二部分，剩下的贡献和剩下的数量其实可以一起算。

记$f_{pos,bn,bm,bk}$表示$pos$位上，$bn$表示$n$有没有达到上界，用于枚举状态，$bm$与$bn$类似。

$bk$比$bn$多出来一个用途就是判断第一部分，如果达到上界了，那么意味着当前枚举的状态可能属于第一部分。

对于多组询问，肯定考虑记忆化啦。

状态的继承可以参照代码。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define gc getchar()
#define ll long long
using namespace std;
const int N=1e5+5;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>
void qw(o x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct node
{
    ll s,c;
    node(ll s=0,ll c=0):s(s),c(c){}
}f[70][2][2][2];bool v[70][2][2][2];int mod;
inline ll add(ll &x,ll y){(x+=y)%=mod;return x;}
inline ll del(ll &x,ll y){(x+=mod-y)%=mod;return x;}
inline int len(ll n){int ans=0;while(n)n>>=1,++ans;return ans;}
ll n,m,k;
node dfs(int pos,int bn,int bm,int bk)
{
    if(!pos)return node(0,1);
    if(v[pos][bn][bm][bk])return f[pos][bn][bm][bk];
    node ans=node(0,0);
    bool fn=(n>>(pos-1))&1,fm=(m>>(pos-1))&1,fk=(k>>(pos-1))&1;
    for(int i=0;i<=(bn?fn:1);++i)
        for(int j=0;j<=(bm?fm:1);++j)//上界限制 
        {
            int t=i^j;
            if(bk&&t<fk)continue;
            node now=dfs(pos-1,bn&&(i==fn),bm&&(j==fm),bk&&(t==fk));
            ans.s=add(ans.s,(1ll<<(pos-1))*t%mod*now.c%mod+now.s);
            ans.c=add(ans.c,now.c);
        }
    v[pos][bn][bm][bk]=1;
    return f[pos][bn][bm][bk]=ans;
}
int main()
{
    int T;qr(T);
    while(T--)
    {
        memset(v,0,sizeof(v));
        qr(n),qr(m),qr(k),qr(mod);n--;m--;
        int ret=max(len(n),max(len(m),len(k)));
        node ans=dfs(ret,1,1,1);
        ll sum=del(ans.s,k%mod*ans.c%mod);
        qw(sum);puts("");
    }
    return 0;
}