#include <stdio.h>
#define NMAX 2005
#define LMAX 1005
char marc[NMAX];
int n,F[21],S[LMAX][LMAX];
void precompute()
{
	int i,j;
	F[0]=1; F[1]=1; marc[1]=1;
	for (i=2; i<=20; i++)
	{
		F[i]=F[i-1]+F[i-2];
		if (F[i]<=2000)
			marc[F[i]]=1;
	}
	int v1,v2,v3;
	for (i=0; i<=1000; i++)
		for (j=0; j<=1000; j++)
		{
			if (i==0)
				v1=0,v3=0;
			else
				v1=S[i-1][j];
			if (j==0)
				v2=0,v3=0;
			else
				v2=S[i][j-1];
			if (i>0 && j>0)
				v3=S[i-1][j-1];
			S[i][j]=v1+v2-v3;
			if (marc[i+j])
				S[i][j]++;
		}
}
int main()
{
	freopen("fibo3.in","r",stdin);
	freopen("fibo3.out","w",stdout);
	precompute();
	scanf("%d",&n);
	int i,x1,y1,x2,y2,rez,v1,v2,v3;
	for (i=1; i<=n; i++)
	{
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		if (x1==0)
			v1=0,v3=0;
		else
			v1=S[x1-1][y2];
		if (y1==0)
			v2=0,v3=0;
		else
			v2=S[x2][y1-1];
		if (x1>0 && y1>0)
			v3=S[x1-1][y1-1];
		rez=S[x2][y2]-v1-v2+v3;
		printf("%d\n",rez);
	}
	return 0;
}