Palkia is playing a popular game called "Lol of Legend". In that game, each player controls 1 champion where each champion has a finite number of skills. These skills can be used to empower other champions.

The main objective of this game is to defeat the enemies with these champions. However, one of Palkia's team member, Eefun, is unable to do that. Eefun only try to make his champions powerful.

Palkia angrily smashes the world where Eefun live with his superpower. Eefun is now stranded in NLC world and he meets Elsee. It turns out that the people of NLC world like playing with riddles and logic puzzles. Long story short, Eefun entered a logic contest and reach the finals. In the finals, Eefun has to solve this problem:

Elsee's father has a quite large coconut farm. The coconuts in this farm have different durabilities. Durability is determined by how high the coconut can be dropped without breaking. If a coconut has 50 durability, then it will break if dropped from 51 height. But, the coconut will not break or damaged if dropped from 50 height. Each coconut has a minimum of 0 and maximum of 2014 durability. Elsee is given two coconuts with the same durability by his father, however Elsee doesn't know their durabilities. Elsee wants to test the durability by dropping them from the window of a building. Worst case scenario, what is the minimum number of times Elsee need to drop the coconuts to know their durabilities? The building Elsee in has a height of 2014.

Eefun can't answer the question so he is eliminated. After the contest, Eefun got the solution from Elsee, which is 63. Eefun is determined to win the logic contest one day.

Palkia is feeling bad after what he's done, then he find another world that is similar to the previous world he destroyed, and he returned every inhabitant from the previous world to that new world. Eefun is sad because he can no longer enter the logic contest in NLC world. Eefun does not want his friendship with Elsee goes to waste so he created programming problem based on the problem that stumped him. Eefun then submits his problem to a programming contest and that problem is used in the contest. Here is the prolem:

Elsee's father has a quite large coconut farm. The coconuts in this farm have different durabilities. Durability is determined by how high the coconut can be dropped without breaking. If a coconut has 50 durability, then it will break if dropped from 51 height. But, the coconut will not break or damaged if dropped from 50 height. Each coconut has a minimum of 0 and maximum of N durability. Elsee is given K coconuts with the same durability by his father, however Elsee doesn't know their durabilities. Elsee wants to test the durability by dropping them from the window of a building. Worst case scenario, what is the minimum number of times Elsee need to drop the coconuts to know their durabilities? The building Elsee in has a height of N.

Input

First line of input contains a number T, the number of test cases. Next T lines each contains N and K, the maximum durability and number of coconuts.

Output

For each test case, output the minimum number of drop test that Elsee must do to find out the coconuts durability.

Example

Input:
3
100 2
2014 2
100000 1 

Output:
14
63
100000 

If you encounter a bug with the custom judge, please let me know in the comment.