#include <fstream>
#include <cstring>
using namespace std;
bool fibo[2001];
int a,b,suma[1002][1002],m,x1,x2,y1,y2,i,termen[2004],n,l,c;
int main()
{
    ifstream fi("fibo3.in");
    ofstream fo("fibo3.out");
    fi>>n;
    memset(termen,0,sizeof(termen));
    memset(fibo,0,sizeof(fibo));
    memset(suma,0,sizeof(suma));
    a=1;
    fibo[1]=fibo[2]=1;

    b=2;
    while(a+b<2000) { c=a+b; a=b; b=c;
    fibo[c]=true; }
      //  for(l=termen[m]-1,c=termen[1];l>0&&c<=n;l--,c++) { mat[l][c]=1; suma[l][c]+=suma[l-1][c]+suma[l][c-1]-suma[l-1][c-1];}

    suma[1][1]=0;
    for(i=2;i<=1001;i++)
    {
        suma[i][1]=suma[1][i]=suma[1][i-1];
        if(fibo[i-1]) suma[i][1]=suma[1][i]=suma[1][i-1]+1;

    }
    for(l=2;l<=1000;l++)
    for(c=2;c<=1000;c++)
    {
        if(fibo[l+c-2]) suma[l][c]=1;
        suma[l][c]+=suma[l-1][c]+suma[l][c-1]-suma[l-1][c-1];
    }

    for(i=1;i<=n;i++)
    {
        fi>>x1>>y1>>x2>>y2;
        x1++; x2++; y1++; y2++;
        fo<<suma[x2][y2]-suma[x1-1][y2]-suma[x2][y1-1]+suma[x1-1][y1-1]<<"\n";
    }
    fo.close();
    return 0;
}