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.

#include <bits/stdc++.h>
using namespace std;

ifstream cin("spp.in");
ofstream cout("spp.out");

long long sp[1500001];

long long CB(long long x, long long p){
    int st = x, dr = 1460000;
    while(st <= dr){
        int mij = (st + dr) / 2;
        if(sp[mij] - sp[x-1] > p)
            dr = mij-1;
        else if(sp[mij] - sp[x-1] < p)
            st = mij+1;
        else
            return mij;
    }
    return st;
}

int main(){
    int n;
    cin >> n;
    long long x, p;
    for(int i = 1; i <= 1460000; ++i)
        sp[i] = 1LL * (sp[i-1] + (1LL * i * i));
    for(int i = 1; i <= n; ++i){
        cin >> x >> p;
        p*=p;
        cout << CB(x, p) << '\n';
    }
    return 0;
}