Choosing Ice Cream

You are standing in a supermarket in front of the freezers, and you have to pick one of the $n$ kinds of ice cream for after dinner. After a while you give up, because they all look good. Instead you take a fair $k$-sided die out of your pocket and let it decide for you.

The number of kinds, $n$, need not equal $k$, so you cannot always throw the die once, read the value $i$, and take the $i$th kind. You need an algorithm that uses zero or more die throws and makes every kind exactly equally likely. The accept-reject method gives such a fair choice.

Then you remember the competition you have to attend that same afternoon. You cannot afford to be late for it. The accept-reject method has no bound on the number of throws it needs before it produces a fair result, so you could stand in front of the freezers for a long time and miss the competition. You therefore want a fair algorithm that uses as few throws as possible in the worst case.

Given $n$ and $k$, determine the smallest number $i$ such that some fair algorithm uses at most $i$ die throws per execution.

The first line contains one positive integer, the number of test cases. This value is at most 100.

Then, per test case:

• one line with two space separated integers $n$ and $k$ ($1 \le n, k \le 10^9$): the number of ice cream kinds and the number of sides of the die.

Per test case:

• one line with a single integer, the smallest number of throws after which a fair choice is guaranteed to be possible. If there is no such number, print unbounded instead.

For $n = 4$ and $k = 20$ one throw is enough.