배스킨라빈스 31

수련회 첫날 밤, 유진이와 규용이는 배스킨라빈스 31 게임을 해서 진 사람이 간장을 마시기로 했다. 게임 규칙은 다음과 같다.

• 유진이와 규용이는 한 줄로 나란히 앉는다. 맨 왼쪽에는 유진이가 앉는다.
• 게임은 유진이부터 시작해 오른쪽으로 진행한다. 즉, 두 사람이 번갈아 가며 차례를 가진다.
• 자기 차례가 되면 1부터 $j$ 사이의 자연수를 앞사람이 말한 수에 이어서 차례대로 1개 이상 $m$개 이하 말할 수 있다. 반드시 1개 이상 말해야 한다.
• $j$를 말하는 사람이 진다.

게임을 여러 번 했지만 계속 유진이만 간장을 마셨다. 화가 난 유진이는 인터넷을 검색해서 반드시 이기는 승리 전략을 찾았다. 전략은 다음과 같다.

• 전체 개수 $j-1$을 $m+1$로 나눈 나머지 $r$을 구한다.
• 수 $r$이 필승 숫자의 초항이다.
• 초항에 $m+1$을 계속 더해 나간 수가 모두 필승 숫자다.
• 게임이 시작되면 첫 차례에 필승 숫자의 초항까지 말한다.
• 이후 상대가 몇 개를 말하든, 자기 차례마다 다음 필승 숫자까지 말하면 게임에서 이긴다.

예를 들어 $j = 31$, $m = 3$이면 $30 = 4 \times 7 + 2$이므로 $r = 2$이고, 필승 숫자는 $2, 6, 10, 14, 18, 22, 26, 30$이다.

유진이가 이 승리 전략대로 게임을 해서 이길 때까지 걸리는 턴 수를 그 게임의 길이라고 하자. 턴 수는 두 사람의 차례를 모두 센 값이며, 마지막에 규용이가 $j$를 말하는 차례도 포함한다. 위의 예에서 유진이는 8번, 규용이도 8번 차례를 가지므로 길이는 16이다.

$n$번의 게임이 주어질 때, 길이가 가장 짧은 게임의 번호와 그 길이를 구하시오.

첫째 줄에 게임의 판 수 $n$이 주어진다. ($1 \le n \le 1{,}000$)

다음 $n$개의 줄에는 각 게임의 정보가 한 줄에 하나씩 주어진다. 각 줄에는 전체 개수이자 말하면 지는 수 $j$와 한 턴에 말할 수 있는 자연수의 최대 개수 $m$이 공백으로 구분되어 주어진다. ($1 \le j \le 10{,}000$, $1 \le m \le 9{,}999$)

단, 항상 $j > m$이고 $j-1$은 $m+1$의 배수가 아니다. 즉, 유진이는 항상 게임에서 이길 수 있다.

길이가 가장 짧은 게임의 번호와 그 길이를 공백으로 구분해 출력한다. 게임 번호는 입력 순서대로 1부터 매긴다. 길이가 가장 짧은 게임이 두 개 이상이면 가장 먼저 입력된 게임의 번호와 그 길이를 출력한다.