== include(page="template/taskheader" task_id="fibo3") ==
Fie şirul numerelor fibonacci:
Fie şirul numerelor Fibonacci:
$F{~0~}=1, F{~1~}=1, F{~2~}=2, F{~3~}=3, F{~4~}=5 etc.$
Vom acoperi toate punctele laticiale de coordonate nenegative astfel:
* Daca pentru un punct $P(x,y), x+y$ este un număr fibonacci, atunci lui $P$ îi asociem valoarea $1$.
* Daca pentru un punct $P(x,y), x+y$ nu este un număr fibonacci, atunci lui $P$ îi asociem valoarea $0$.
* Daca pentru un punct $P(x,y), x+y$ este un număr Fibonacci, atunci lui $P$ îi asociem valoarea $1$.
* Daca pentru un punct $P(x,y), x+y$ nu este un număr Fibonacci, atunci lui $P$ îi asociem valoarea $0$.
h2. Cerinţă
Răspundeţi la $N$ întrebări de forma:
Dându-se un dreptunghi $D(x{~1~}, y{~1~}, x{~2~}, y{~2~})$, care este suma valorilor asociate punctelor din plan conţinute de dreptunghiul $D$?
Răspundeţi la $N$ întrebări de forma: _Dându-se un dreptunghi $D(x{~1~}, y{~1~}, x{~2~}, y{~2~})$, care este suma valorilor asociate punctelor din plan conţinute de dreptunghiul $D$?_
h2. Date de intrare
Fişierul de intrare $fibo3.in$ conţine pe prima linie numărul $N$ de întrebări.
Liniile de la $2$ la $N+1$ vor conţine câte patru numere naturale reprezentând câte un dreptunghi de query.
Fişierul de intrare $fibo3.in$ conţine pe prima linie numărul $N$ de întrebări. Următoarele $N$ linii vor conţine câte patru numere naturale reprezentând câte un dreptunghi de query.
h2. Date de ieşire
În fişierul de ieşire $fibo3.out$ se vor găsi $N$ numere naturale, fiecare pe câte o linie, numărul de pe linia $K$ fiind răspunsul la a $K$-a întrebare.
În fişierul de ieşire $fibo3.out$ se vor găsi $N$ numere naturale, fiecare pe câte o linie, numărul de pe linia $K$ fiind răspunsul la cea de-a $K$-a întrebare.
h2. Restricţii
* $0 ≤ x{~1~} ≤ x{~2~} ≤ 10^15^$
* $0 ≤ y{~1~} ≤ y{~2~} ≤ 10^15^$
* Un punct $P(x,y)$ se numeşte punct laticial, dacă $x$ şi $y$ sunt numere întregi.
* Pentru $30%$ din teste coordonatele dreptunghiurilor sunt maxim $1000$.
* Sirul numerelor Fibonacci este determinat de recurenţa $F{~N~} = F{~N-1~} + F{~N-2~}$
* Pentru $30%$ din teste coordonatele dreptunghiurilor nu depăşesc $1000$.
h2. Exemplu
