Baskin-Robbins 31

On the first night of a retreat, Yujin and Gyuyong play the Baskin-Robbins 31 game, and the loser has to drink soy sauce. The rules are as follows.

• Yujin and Gyuyong sit side by side in a row. Yujin sits at the far left.
• The game starts with Yujin and proceeds to the right, so the two players take turns alternately.
• On your turn, you say between 1 and $m$ consecutive natural numbers from 1 to $j$, continuing from the last number said. You must say at least one number.
• The player who says $j$ loses.

They played several times, but Yujin kept drinking the soy sauce. Annoyed, Yujin searched the internet and found a strategy that always wins. The strategy is:

• Divide the total count $j-1$ by $m+1$ and take the remainder $r$.
• The number $r$ is the first winning number.
• Adding $m+1$ to it again and again gives all the winning numbers.
• When the game starts, say numbers up to the first winning number.
• After that, no matter how many numbers the opponent says, say numbers up to the next winning number on each of your turns, and you win.

For example, if $j = 31$ and $m = 3$, then $30 = 4 \times 7 + 2$, so $r = 2$ and the winning numbers are $2, 6, 10, 14, 18, 22, 26, 30$.

Define the length of a game as the number of turns it takes until Yujin wins by following this strategy. The count includes the turns of both players, including Gyuyong's final turn in which he says $j$. In the example above, Yujin has 8 turns and Gyuyong has 8 turns, so the length is 16.

Given $n$ games, find the number of the shortest game and its length.

The first line contains the number of games $n$ ($1 \le n \le 1{,}000$).

Each of the next $n$ lines describes one game. It contains $j$, the total count and the number whose speaker loses, and $m$, the maximum count of natural numbers that can be said in one turn, separated by a space ($1 \le j \le 10{,}000$, $1 \le m \le 9{,}999$).

It is guaranteed that $j > m$ and that $j-1$ is not a multiple of $m+1$. In other words, Yujin can always win.

Print the number of the shortest game and its length, separated by a space. Games are numbered from 1 in input order. If two or more games share the shortest length, print the number of the one that appears first in the input, together with its length.