The Magic Potion

Mingyun spends his days working out how to be found cute. His neighbor Jiho told him that anyone who reaches the Land of Wonder gets an unlimited supply of it. Jiho refuses to hand over the route for free, so he proposes the following game.

There are $N$ bags. Exactly one of them holds an unlimited supply of the magic potion that sends a person to the Land of Wonder, and every other bag holds an unlimited supply of pills that do nothing. The bags can be told apart, but the pills inside them all look the same. Anyone who takes the magic potion leaves for the Land of Wonder at once.

Mingyun runs an experiment to find out which bag holds the magic potion. Before the experiment starts he invites as many friends as he wants, and the experiment runs in several rounds. In each round he picks any friends who have not left yet and feeds them pills from any bags he chooses. He may give a friend no pill at all, and he may give one friend pills from several bags. A friend who takes the magic potion and leaves cannot take part from the next round on. At the end of a round Mingyun learns which friends disappeared in that round, and he decides who takes which pills in the next round after seeing that result.

For example, take 10 bags and 2 rounds. The simplest plan is to invite 10 friends and give each of them one bag, which settles the answer in a single round. Three friends are enough, though. In the first round, feed friend 1 the pills from bags 1, 2, 3, feed friend 2 the pills from bags 4, 5, 6, and feed friend 3 the pills from bags 7, 8, 9. If nobody disappears, the answer is bag 10. If friend 1 disappears, the answer is one of bags 1, 2, 3, so in the second round feed friend 2 the pills from bag 1 and feed friend 3 the pills from bag 2. Friend 2 disappearing means bag 1, friend 3 disappearing means bag 2, and nobody disappearing means bag 3. With only 2 friends, no plan finds the bag within 2 rounds.

Given the number of bags $N$ and the number of rounds $E$, find the smallest number of friends $F$ that always identifies the bag holding the magic potion within $E$ rounds. Jiho stops the game the moment Mingyun answers anything other than the minimum, so report exactly the minimum.

The first line contains the number of queries $T$ ($1 \le T \le 100$). Each of the next $T$ lines contains $N$ ($1 \le N \le 10^6$) and $E$ ($1 \le E \le 10$), separated by a space.

For each query, print the smallest number of friends $F$ on its own line.