Rezolvare PBinfo #4368

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.