Gourmet Games

Wolfgang Puck is opening a new exclusive restaurant in Las Vegas and is looking for a chef. His nephew Hansel caught him thinking of posting an ad in newspapers. (Note: Wolfgang has heard of “this Internet thingy” but didn't find it interesting, because one could not spread some Internet on a piece of bread, which is the mere minimum that has to be satisfied for something to be interesting, according to Mr. Puck.)

Hansel knows what the advantages of the Internet job postings are, but he came up with an even better idea: given the success of various reality TV shows and given the fact that the restaurant is opening in Las Vegas, why not organize a sort of a cook-off tournament that will decide who Mr. Puck will hire?

The idea basically combines the Iron Chef™ show with the World Series Of Poker™: In every show, m cooks prepare a five-course meal for judges, and the best one (according to the judges) advances to the next round. All candidates are ranked based on the previous experience, so even if the number of the candidates is not divisible by m, some of them can get a bye and compete in later rounds. The winner of the final show gets the honor of being the chef in the best Wolfgang Puck's restaurant ever.

Hansel realized that even with the byes, it might not be possible to hold a tournament with m chefs per show, so he is trying to find out what the best m for the given number of candidates is. If you can just help him by letting him know if he can run a tournament as described with n candidates and m chefs per show, and in the case he can, how many shows he needs, he will be so grateful that he might even convince Mr. Puck to share the Secret Cheesecake Base Recipe with you.

Input Specification

The input starts with a line containing a single integer t, the number of test cases. The next t lines each contain two integers separated by spaces, n and m (2 ≤ n ≤ 10000, 2 ≤ m ≤ n), where n is the total number of candidates, and m is the number of chefs participating in a single TV show.

Output Specification

For each test case, print the number of shows that need to be run to get the new chef. In the case that the tournament cannot be run with the given n and m, print “cannot do this”.

Sample Input

1. 3
2. 3 2
3. 4 3
4. 4 4

download as text file

Output for Sample Input

1. 2
2. cannot do this
3. 1

download as text file