Олимпиадный тренинг

Задача . C. Бан в чате

Задача

Вы — совершенно обычный пользователь чата на самой известной стриминговой платформе. Конечно же, в некоторые моменты вам просто хочется отдохнуть, расслабиться и поспамить что-то в чат.

Точнее говоря, вы хотите отправить в чат треугольник из эмоутов размера $k$. Такой треугольник состоит из $2k-1$ сообщений. Первое сообщение состоит из одного эмоута, второе — из двух эмоутов, ..., $k$-е — из $k$ эмоутов, $k+1$-е — из $k-1$ эмоутов, ..., и последнее — из одного эмоута.

Например, треугольник из эмоутов для $k=3$ состоит из $5$ сообщений:

$\text{[math]}$

Конечно же, большинство каналов имеют автоматическую модерацию. Автомодератор забанит вас сразу же после того, как вы отправите хотя бы $x$ эмоутов подряд (можете считать, что вы — единственный пользователь чата). Теперь вам интересно — как много сообщений вы успеете отправить перед тем, как вас забанят? А может быть, вас не забанят вовсе (то есть вы напишете все $2k-1$ сообщений и успешно отправите в чат треугольник из эмоутов)? Заметьте, что если вас банят после написания какого-то сообщения, то это сообщение также учитывается.

Вам необходимо ответить на $t$ независимых наборов тестовых данных.

Входные данные

Первая строка входных данных содержит одно целое число $t$ ($1 \le t \le 10^4$) — количество наборов тестовых данных. Следующие $t$ строк описывают сами наборы.

Единственная строка набора тестовых данных содержит два числа $k$ и $x$ ($1 \le k \le 10^9; 1 \le x \le 10^{18}$).

Выходные данные

Выведите ответ на каждый набор тестовых данных — количество сообщений, которые вы напишете перед тем, как вас забанят, для соответствующих значений $k$ и $x$.

Примечание

Давайте проанализируем наборы тестовых данных примера.

В первом наборе тестовых данных вы пишете три сообщения, состоящие из $1$, $2$ и $3$ эмоутов соответственно, и так как $1 + 2 + 3 \ge 6$, после этого вы получаете бан.
Во втором наборе тестовых данных вы пишете четыре сообщения, состоящие из $1$, $2$, $3$ и $4$ эмоутов соответственно, и так как $1 + 2 + 3 + 4 \ge 7$, после этого вы получаете бан.
В третьем наборе тестовых данных, вы пишете одно сообщение, состоящее из $1$ эмоута. Это не приводит к бану, потому что $1 < 2$, но вы уже закончили спам треугольника из эмоутов. Таким образом, вы успешно написали одно сообщение.
В четвертом наборе тестовых данных вы пишете четыре сообщения, состоящие из $1$, $2$, $3$ и $2$ эмоутов соответственно, и так как $1 + 2 + 3 + 2 \ge 7$, после этого вы получаете бан.
В пятом наборе тестовых данных вы пишете три сообщения, состоящие из $1$, $2$ и $1$ эмоутов соответственно. Это не приводит к бану, потому что $1 + 2 + 1 < 5$, но вы уже закончили спам треугольника из эмоутов. Таким образом, вы успешно написали три сообщения.
В шестом наборе тестовых данных, так как $x = 1$, вы получаете бан сразу же после того, как напишете свое первое сообщение.
Седьмой набор тестовых данных слишком большой, чтобы его анализировать, так что мы его пропустим.

Примеры

№	Входные данные	Выходные данные
1	7 4 6 4 7 1 2 3 7 2 5 100 1 1000000000 923456789987654321	3 4 1 4 3 1 1608737403

time 2000 ms
memory 512 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	5

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет