eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Выбор мороженого

Выбор мороженого

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Вы находитесь в супермаркете перед морозильниками. Перед Вами стоит очень сложная задача: следует выбрать тип мороженого, которое Вы хотите съесть после обеда в тот вечер. Через некоторое время Вы сдаетесь: все мороженое потрясающее! Вместо этого Вы достаете из кармана свой (справедливый) k - сторонний кубик, и позволяете судьбе решить задачу.

Конечно, количество вариантов выбора мороженого n может не совпадать с k, в этом случае Вы не можете просто бросить кубик один раз, получив число i, и взяв i - ый тип мороженого. Поэтому Вам следует использовать какой-то алгоритм, который включает в себя нуль или более бросков, приводящий к выбору мороженого, где каждый выбор будет в равной степени вероятным. Будучи хорошим ученым-программистом, Вы знаете о методе accept-reject, который позволит Вам сделать такой честный выбор.

В данный момент Вы вспоминаете, что сегодня у Вас очень важное соревнование. Вы абсолютно не можете позволить себе опоздать на этот конкурс. Из-за этого Вы решаете, что не можете использовать метод accept-reject, так как не может быть никаких ограничений на количество бросков, необходимых для обеспечения справедливого результата, поэтому Вы можете долго быть заняты и пропустить соревнование! Поэтому Вы решаете найти подходящий честный алгоритм, который использует как можно меньше бросков кубиков в худшем случае.

По заданным n и k следует определить наименьшее число i, для которого существует справедливый алгоритм, который совершает не более i бросков кубика для решения задачи.

prb8327.gif

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

Первая строка содержит количество тестов, не большее 100. Далее для каждого теста:

  • в одной строке два целых числа n и k (1n, k10^9): количество выборов мороженого и число граней на Вашем кубике.

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

Для каждого теста выведите в отдельной строке наименьшее количество бросков, после которых Вы гарантированно сможете сделать правильный выбор. Если такого количества не существует, выведите "unbounded".

Пример

Входные данные #1
3
4 2
2 4
3 2
Выходные данные #1
2
1
unbounded
Источник 2014 Benelux Algorithm Programming Contest (BAPC), Preliminaries, Problem A