Fişierul intrare/ieşire:	fibo3.in, fibo3.out	Sursă	Stelele Informaticii 2010
Autor	Serban Andrei Stan	Adăugată de	Serban Andrei Stan •savim
Timp execuţie pe test	0.25 sec	Limită de memorie	10096 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Fibo3

Fie şirul numerelor fibonacci:
F₀=1, F₁=1, F₂=2, F₃=3, F₄=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.

Cerinţă

Răspundeţi la N întrebări de forma:
Dându-se un dreptunghi D(x₁, y₁, x₂, y₂), care este suma valorilor asociate punctelor din plan conţinute de dreptunghiul D?

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.

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.

Restricţii

• 1 ≤ N ≤ 100 000
• 0 ≤ x₁ ≤ x₂ ≤ 10¹⁵
• 0 ≤ y₁ ≤ y₂ ≤ 10¹⁵
• 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.

Exemplu

Cum se trimit solutii?