Rezolvare PBinfo #3401

După o zi plină, trei băieți se joacă cu numere. În fiecare seară, unul dintre ei alege un număr x, iar altul un număr y mai mare sau egal cu x. Al treilea propune ceva mai interesant. Astfel, el alege să le spună aproape instantaneu suma pătratelor perfecte de la x și y. Voi trebuie să rezolvați ceva asemănător, doar că știți numai ce zice primul și ultimul băiat. Pentru a-i verifica dacă greșesc la calcule, în schimb, trebuie să găsiți numărul pe care l-ar putea spune al doilea.

Formal, pentru două numere x și y se definește SPP(x,y) = x2 + (x+1)2 +...+ y2 (suma pătratelor perfecte de la x la y).

Se dau Q întrebări de tipul x p și se cere cel mai mic y mai mare sau egal ca x pentru care SPP(x,y) ≥ p2.

Cerința

Să se calculeze pentru fiecare întrebare p minimum, pentru care relația este satisfăcută.

Date de intrare

Fișierul de intrare spp.in conține pe prima linie un număr natural Q. Pe liniile 2, 3, …, Q+1 se află câte o pereche x p care satisface restricțiile.

Date de ieșire

Fișierul de ieșire spp.out va conține răspunsul la fiecare întrebare.

Restricții și precizări

• Q ≤ 100.000
• 1 ≤ x ≤ 100.000
• 1 ≤ p ≤ 1.000.000.000
• Pentru 30% din teste, Q ≤ 100 sau p ≤ 1000

Exemplu:

spp.in

2
1 5
10 19

spp.out

4
12

Explicație

12 + 22 + 32 + 42 = 30 ≥ 52.
102 + 112 + 122 = 365 ≥ 192.