E. Насквозь бюрократическая организация
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

На прием в недавно открывшуюся, но уже насквозь бюрократическую организацию (сокращенно НБО) одновременно записались n человек. Поскольку организация насквозь бюрократическая, в каждый день она способна принять и обслужить ровно одного человека. Как следствие, каждому из n человек был назначен прием в один из последующих n дней, причем ни у каких двух людей день приема не совпадает.

Однако работники организации подходят к работе весьма безответственно, поэтому ни одному из записавшихся людей не была сказана дата приема. Единственный способ узнать, в какие дни нужно приходить определенной группе людей — писать заявления-запросы в НБО.

Бланк одного заявления-запроса состоит из m пустых строчек, в каждую из которых можно вписать имя некоторого человека из записавшихся на прием (а можно оставить пустой). При этом нельзя записывать одного и того же человека на одном заявлении дважды, иначе такой запрос игнорируется. На такие запросы в письменном виде НБО всегда отвечает очень быстро, зато некачественно — а именно, в ответ приходят верные даты приема указанных на бланке людей, однако в совершенно случайном порядке. При этом ответы на все поданные заявления-запросы приходят одновременно в конце дня (на каждом ответе указано, на какое именно заявление это ответ).

К счастью, вы не входите в группу этих n счастливчиков. Ваша задача как стороннего наблюдателя — по заданным n и m определить, какое минимальное количество заявлений нужно подать в НБО, чтобы однозначно определить дату приема каждого человека.

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

В первой строке содержится целое число t (1 ≤ t ≤ 1000) — количество тестовых случаев. В каждой из следующих t строк содержатся два числа n и m (1 ≤ n, m ≤ 109) — количество людей, записавшихся на прием в НБО, и количество пустых строчек в заявлении-запросе, соответственно.

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

Выведите t строк, в каждой из которых расположен ответ на соответствующий тестовый случай (в порядке ввода) — минимальное количество заявлений, которое необходимо подать в НБО.

Примеры
Входные данные
5
4 1
4 2
7 3
1 1
42 7
Выходные данные
3
2
3
0
11
Примечание

В первом примере нужно сделать три запроса в НБО, указав в них трех разных людей. Узнав их даты приема, методом исключения можно узнать дату приема четвертого человека, поэтому четвертый запрос не нужен.

Во втором примере достаточно двух заявлений. Пронумеруем людей от 1 до 4 и в первом укажем людей 1 и 2, а во втором — людей 1 и 3. Несложно убедиться, что дату приема каждого человека теперь можно однозначно определить независимо от того, какие ответы получены из НБО.

В четвертом примере на прием записался всего один человек. Никаких заявлений ему подавать не надо — он записан на завтра.