Problem E. You Jump I Jump

Problem

"You jump, I jump, remember?" Jack said. Then Jack jumped down from a tower and he was gone. Rose was heartbroken and she felt Jack's true love.

Is that the end of the story? No! Jack is still alive and comes to tell Rose "Don't jump anymore."

In fact, Jack has to do a lot of testing before he jumps. He wants to find out the highest floor m from which he jumps to the ground and stays alive. He knows the tower has n floors. Before Rose arrives and meets him, he only has enough time to do k test jumps. Now, he needs to buy "dummy bodies" for testing. He then tries to drop the dummy bodies one at a time from different floors. Dummy bodies are very similar to Jack's body. Specifically, a dummy body dropped from the i th floor will have two outcomes:

1. If Jack will die jumping from the i th floor, the dummy body will break into pieces.
2. Otherwise, the dummy body will not break into pieces, and it can be reused in another test jump.

Now, he wants to know the least number of dummy bodies he needs to buy to guarantee that the value of m can be found no matter what it is. Could you help Jack to solve this problem?

Input

The first line contains an integer, specifying the number of test cases. There will be at most 10000 cases. For each case, there will be only one line with two integers n and k where 0 ≤ n ≤ 250 and 0 ≤ k ≤ 250.

Output

For each test case, output an integer (on its own line) specifying the minimum number of dummy bodies Jack needs to buy. If it cannot be guaranteed to find out the value of m by only k jumps for a tower with n floors, print out a line "impossible".

Sample Input

10
0 0
0 1
1 0
1 1
8 3
8 4
8 5
8 6
8 7
8 8

Sample Output

0
0
impossible
1
impossible
2
2
2
2
1

Remark 1: Jack will never die if he jumps from ground floor. XD
Remark 2: The sample solution can handle 0 ≤ n,k < 2³². Leave it as your homework. :)

Author