Вы — совершенно обычный пользователь чата на самой известной стриминговой платформе. Конечно же, в некоторые моменты вам просто хочется отдохнуть, расслабиться и поспамить что-то в чат.
Точнее говоря, вы хотите отправить в чат треугольник из эмоутов размера $$$k$$$. Такой треугольник состоит из $$$2k-1$$$ сообщений. Первое сообщение состоит из одного эмоута, второе — из двух эмоутов, ..., $$$k$$$-е — из $$$k$$$ эмоутов, $$$k+1$$$-е — из $$$k-1$$$ эмоутов, ..., и последнее — из одного эмоута.
Например, треугольник из эмоутов для $$$k=3$$$ состоит из $$$5$$$ сообщений:
Конечно же, большинство каналов имеют автоматическую модерацию. Автомодератор забанит вас сразу же после того, как вы отправите хотя бы $$$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$$$.
7 4 6 4 7 1 2 3 7 2 5 100 1 1000000000 923456789987654321
3 4 1 4 3 1 1608737403
Давайте проанализируем наборы тестовых данных примера.
- В первом наборе тестовых данных вы пишете три сообщения, состоящие из $$$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$$$, вы получаете бан сразу же после того, как напишете свое первое сообщение.
- Седьмой набор тестовых данных слишком большой, чтобы его анализировать, так что мы его пропустим.
