#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#define NRMAX 1000000000000000LL
#define MAX 100
#define x first
#define y second

using namespace std;
typedef long long ll;

ll n,x1,y1,x2,y2,nrt,xi,yi,sz1,sz2,ans;
ll nrfb[MAX];
pair<ll,ll> intersectii[4],iok[2];

int main()
{
    ifstream f ("fibo3.in");
    ofstream g ("fibo3.out");
    f>>n;
    nrfb[0]=nrfb[1]=1; nrt=1;
    for(ll i=nrfb[nrt]+nrfb[nrt-1];i<=NRMAX;i=i+nrfb[nrt-1])
      nrfb[++nrt]=i;
//    for(int i=1;i<=nrt;i++) cout<<nrfb[i]<<" ";
//    cout<<"\n\n";
//    cout<<nrfb[40]<<"\n\n";
    while(n--){
      f>>x1>>y1>>x2>>y2;
      ans=0;
      for(ll i=1;i<=nrt;i++){
        //cout<<i<<" "<<nrfb[i]<<'\n';
        if(x1+y1<=nrfb[i] && nrfb[i]<=x2+y2){
          sz1=0;
          //cout<<nrfb[i]<<" ";
          yi=(nrfb[i]-x1); intersectii[sz1++]=(make_pair(x1,yi));//x1
          xi=(nrfb[i]-y1); intersectii[sz1++]=(make_pair(xi,y1));//y1
          yi=(nrfb[i]-x2); intersectii[sz1++]=(make_pair(x2,yi));//x2
          xi=(nrfb[i]-y2); intersectii[sz1++]=(make_pair(xi,y2));//y2
          sort(intersectii+0,intersectii+4);
          sz2=0;
          for(ll j=0;j<4;j++){
            xi=intersectii[j].x,yi=intersectii[j].y;
            if(xi>=x1&&xi<=x2&&yi>=y1&&yi<=y2&&(j==3||intersectii[j]!=intersectii[j+1]))
              iok[sz2++]=(intersectii[j]);
          }
//          cout<<i<<" "<<(nrfb[i])<<": "<<sz2<<'\n';
          if(sz2==1)ans++;
          else if(sz2==2)ans+=iok[1].x-iok[0].x+1;
        }
      }
      g<<ans<<'\n';
      //cout<<"\n\n\n";
    }
//    cout<<nrfb[40];
    f.close ();
    g.close ();
    return 0;
}