Cerința
Dorel este pasionat de studiul pătratelor perfecte. El doreşte să afle răspunsul la Q
cerinţe de forma: dacă se dau numerele naturale l
, r
, a
, b
, cu l ≤ r
, să se afle câte numere naturale x
cuprinse între l
şi r
(inclusiv acestea) au proprietatea că x+a
şi x+b
sunt simultan pătrate perfecte.
Date de intrare
Pe prima linie a intrării standard se află numărul Q
, iar pe următoarele Q
linii se află câte patru valori l
, r
, a
, b
, separate prin spaţiu.
Date de ieșire
La ecran se vor afişa, pe linii diferite, răspunsurile la cele Q
cerinţe ale lui Dorel.
Restricții și precizări
1 ≤ Q ≤ 100.000
1 ≤ l ≤ r ≤ 2.000.000.000
1 ≤ a < b ≤ 1.000.000
Exemplu:
Intrare
3 1 9 3 10 13 780 4 61 35 789 4 3279
Ieșire
1 2 0
Explicație
Pentru primul exemplu, între numerele 1
şi 9
există o singură valoare a lui x
pentru care numerele x+3
şi x+10
să fie simultan pătrate perfecte, şi anume x=6
.
Pentru al doilea exemplu, între numerele 13
şi 780
există două valori ale lui x
pentru care numerele x+4
şi x+61
să fie simultan pătrate perfecte, şi anume x=60
şi x=780
.