El dilema del pico

Entrada

La primera línea contiene un único entero $t$ $(1 \leq t \leq 1 0^{4})$ (1 \le t \le 10^4) – el número de casos de prueba.

La única línea de cada caso de prueba contiene dos enteros $n$ y $k$ $(1 \leq n \leq 1 0^{9}, 1 \leq k \leq 1 0^{18})$ (1 \le n \le 10^9 \, , \, 1 \le k \le 10^{18}).

Se garantiza que existe al menos un arreglo válido.

Salida

Para cada caso de prueba, muestra un único entero – el máximo valor posible de $a_{n}$ a_n.

¡Ten en cuenta! que los valores no caben en un tipo entero de 32 bits, por lo que debes usar al menos un tipo entero de 64 bits en tu lenguaje de programación (como long long en C++).

Ejemplos

Ejemplo 1

Loading

Nota

En el primer caso de prueba, el arreglo es $[5]$ , y $i = 1 \sum 1 j = i \sum 1 a_{j} = a_{1} = 5$ \sum\limits_{i=1}^{1}\sum\limits_{j=i}^{1} a_j=a_1=5, por lo que $a_{1} = 5$ a_1=5.

En el segundo caso de prueba, el arreglo $[1, 7]$ maximiza $a_{2}$ a_2, tenemos

$i = 1$ i=1 : $1 + 7 = 8$ 1+7=8.
$i = 2$ i=2 : $7$ .

por lo tanto la suma es $8 + 7 = 15$ 8+7=15, y $a_{2} = 8$ a_2=8 es imposible, ya que $8 + 8 = 16 > 15$ 8+8=16>15 de por sí.

En el tercer caso de prueba, el arreglo $[3, 1, 3]$ [3,1,3] maximiza $a_{3}$ a_3, tenemos

$i = 1$ i=1 : $3 + 1 + 3 = 7$ 3+1+3=7.
$i = 2$ i=2 : $1 + 3 = 4$ 1+3=4.
$i = 3$ i=3 : $3$ .

por lo tanto la suma es $7 + 4 + 3 = 14$ 7+4+3=14, y $a_{3} = 4$ a_3=4 es imposible, ya que incluso $[1, 1, 4]$ [1,1,4] da $6 + 5 + 4 = 15 > 14$ 6+5+4=15>14.

Puntuación

Subtarea $1$ ( $20$ puntos) : $(n = 1)$ (n=1)
Subtarea $2$ ( $30$ puntos) : $(\sum n \leq 1000, k \leq 1 0^{6})$ (\sum n \le 1000 \, , \, k \le 10^6)
Subtarea $3$ ( $100$ puntos) : Sin restricciones adicionales.