spp

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) = x^2+(x+1)^2+...+y^2$ (suma pătratelor perfecte de la $x$ la $y$).

Se dau $Q$ întrebări de genul x p și se cere cel mai mic $y$ mai mare sau egal ca $x$ pentru care $SPP(x,y) \geq p^2$.

Cerință

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

Date de intrare

Pe prima linie din fișierul spp.in se află 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 query.

Restricții și precizări

• $1 \leq Q \leq 10^5$;
• $1 \leq x \leq 10^5$;
• $1 \leq p \leq 10^9$;
• Pentru 30% din teste, $Q \leq 100$ sau $p \leq 10^3$.

Exemplu

spp.in

2
1 5
10 19

spp.out

4
12

Explicație

• $1^2 + 2^2 + 3^2 + 4^2 = 29 \geq 5^2$;
• $10^2 + 11^2 + 12^2 = 385 \geq 19^2$.