Дилема піку

Вхідні дані

Перший рядок містить одне ціле число $t$ $(1 \leq t \leq 1 0^{4})$ (1 \le t \le 10^4) – кількість тестових випадків.

Єдиний рядок кожного тестового випадку містить два цілих числа $n$ і $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}).

Гарантується, що існує принаймні один коректний масив.

Вихідні дані

Для кожного тестового випадку виведіть одне ціле число – максимально можливе значення $a_{n}$ a_n.

Зверніть увагу! Значення не вміщуються у 32-бітний цілочисельний тип, тому вам слід використовувати щонайменше 64-бітний цілочисельний тип у вашій мові програмування (наприклад, long long у C++).

Приклади

Приклад 1

Loading

Примітка

У першому тестовому випадку масив дорівнює $[5]$ , і $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, отже $a_{1} = 5$ a_1=5.

У другому тестовому випадку масив $[1, 7]$ максимізує $a_{2}$ a_2, маємо

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

отже сума дорівнює $8 + 7 = 15$ 8+7=15, а $a_{2} = 8$ a_2=8 неможливе, оскільки вже $8 + 8 = 16 > 15$ 8+8=16>15.

У третьому тестовому випадку масив $[3, 1, 3]$ [3,1,3] максимізує $a_{3}$ a_3, маємо

$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$ .

отже сума дорівнює $7 + 4 + 3 = 14$ 7+4+3=14, а $a_{3} = 4$ a_3=4 неможливе, оскільки навіть $[1, 1, 4]$ [1,1,4] дає $6 + 5 + 4 = 15 > 14$ 6+5+4=15>14.

Оцінювання

Підзадача $1$ ( $20$ балів) : $(n = 1)$ (n=1)
Підзадача $2$ ( $30$ балів) : $(\sum n \leq 1000, k \leq 1 0^{6})$ (\sum n \le 1000 \, , \, k \le 10^6)
Підзадача $3$ ( $100$ балів) : Без додаткових обмежень.