#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

typedef long long ll;

ll n,m,K,P;

ll ans,cnt,sum;

ll f[70][2][2][2],g[70][2][2][2];

inline ll rd()

{

	ll ret=0;	char gc=getchar();

	while(gc<'0'||gc>'9')	gc=getchar();

	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();

	return ret;

}

void work()

{

	n=rd(),m=rd(),K=rd(),P=rd();

	int i,a,b,c,x,y,z,A,B,C;

	ll ni,mi,ki;

	memset(f,0,sizeof(f)),memset(g,0,sizeof(g));

	f[61][1][1][1]=1;

	for(i=60;i>=0;i--)	for(a=0;a<=1;a++)	for(b=0;b<=1;b++)	for(c=0;c<=1;c++)	if(f[i+1][a][b][c])

	{

		ni=(n>>i)&1,mi=(m>>i)&1,ki=(K>>i)&1;

		for(x=0;x<=1;x++)	if(!a||x<=ni)	for(y=0;y<=1;y++)	if(!b||y<=mi)

		{

			z=x^y;

			if(c&&z<ki)	continue;

			A=a&&x==ni,B=b&&y==mi,C=c&&z==ki;

			f[i][A][B][C]=(f[i][A][B][C]+f[i+1][a][b][c])%P;

			g[i][A][B][C]=(g[i][A][B][C]+g[i+1][a][b][c])%P;

			if(z)	g[i][A][B][C]=(g[i][A][B][C]+(1ll<<i)%P*f[i+1][a][b][c]%P)%P;

		}

	}

	printf("%lld\n",(g[0][0][0][0]-K%P*f[0][0][0][0]%P+P)%P);

}

int main()

{

	int T=rd();

	while(T--)	work();

	return 0;

}