STEVE - Voracious Steve

Steve and Digit bought a box containing a number of donuts. In order to divide them between themselves they play a special game that they created. The players alternately take a certain, positive number of donuts from the box, but no more than some fixed integer. Each player's donuts are gathered on the player's side. The player that empties the box eats his donuts while the other one puts his donuts back into the box and the game continues with the "loser" player starting. The game goes on until all the donuts are eaten. The goal of the game is to eat the most donuts. How many donuts can Steve, who starts the game, count on, assuming the best strategy for both players?

Task

Write a program that:

  • reads the parameters of the game from the standard input,
  • computes the number of donuts Steve can count on,
  • writes the result to the standard output.

Input

The input begins with the integer t, the number of test cases. Then t test cases follow.

For each test case the first and only line of the input contains exactly two integers n and m separated by a single space, 1 <= m <= n <= 100 - the parameters of the game, where n is the number of donuts in the box at the beginning of the game and m is the upper limit on the number of donuts to be taken by one player in one move.

Output

For each test case the output contains exactly one integer equal to the number of donuts Steve can count on.

Example

Sample input:
1
5 2 

Sample output:
3

Added by:adrian
Date:2004-07-07
Time limit:7s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:ACM Central European Programming Contest, Warsaw 2002

hide comments
2015-08-11 23:12:31 Khaled El-Tahan
Good problem :D
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.