Alice and Bob love games, but they have already played every single game available at their local Games ’R U (Games foR U) store. Tired of playing the same games over and over again, and from not receiving news from the game store, they decided to create their own game. After a few weeks of hard intellectual work Alice came up with Guessing Game, a two player game consisting in Alice picking a number and letting Bob try to guess it. Before playing the game, Alice and Bob agree in the size of the game, given by two integer positive numbers, the range N and the limit of strikes S. Alice chooses a secret integer number X, 0 ≤ X < N. Then Bob uses turns telling Alice integer numbers in order to guess her choice. Each Bob’s guess is answered by Alice with a strike, if Bob’s number is greater than X, with a smile, if Bob’s number is less than X, or with a stop, if Bob’s number is precisely X. In this last case the game ends and Bob wins. If Bob receives S strikes the game ends with Alice as winner. Bob is very competitive. He wants to develop a winning strategy and he starts trying to do it in the case N = 3 and S = 2. He notes that guessing 1 in the first turn suffices to win: if he receives a strike, Alice’s number must be 0 and he can guess it in the next turn; if Alice’s number is 1, he already wins; otherwise, he receives a smile, and Alice’s number must be 2. Either way he manages to guess the right number without receiving 2 strikes. Before facing Alice in an official match, Bob asks for a little help with his training. Indeed, he wants you to make a program that computes the minimum number of guesses needed by him to guess any number X, 0 ≤ X < N, receiving at most S − 1 strikes. Input Input consists of several test cases. The first line of the input file contains a number C specifying the number of cases in the file. Then C lines follow, each one containing two integer numbers N and S, separated by a blank and representing the range and the limit of strikes of a Guessing Game, respectively. You may assume that 1 ≤ N ≤ 1000 and 1 ≤ S ≤ 20. Output For each test case, a single line containing an integer number indicating the minimum number of guesses needed by Bob to guess every possible number picked by Alice. Sample Input 3 51 32 72 Sample Output 5 2 4