소수 게임

Alice와 Bob은 "소수 게임"을 즐겨 한다.

소수 게임에서는 두 사람이 먼저 연속된 정수 구간을 고른다. 그다음 구간에 속한 정수마다 미니 게임을 한 번씩 한다.

규칙은 다음과 같다.

• 먼저 Alice가 정수 $A$와 $k$를 고른다. 이때 $2 \le k \le A-1$을 만족해야 한다. $k$는 미니 게임을 몇 번 할지 정하고, $A$는 구간의 상한을 정한다.
• 다음으로 Bob이 정수 $x$를 고른다. 이때 $2 \le x \le A+1-k$를 만족해야 한다. $x$는 구간의 하한을 정하므로, 구간은 $x$ 이상 $A$ 이하가 된다.
• 두 사람은 $x$ 이상 $x+k-1$ 이하의 정수 $N$마다 미니 게임을 한 번씩 한다. 각 미니 게임은 다음과 같이 진행한다.
  • 종이에 $N$을 적는다($x \le N \le x+k-1$). 그다음 Alice와 Bob이 번갈아 플레이한다.
  • 자신의 차례에 Alice는 종이에 적힌 수 이하의 소수 $P$를 고른다.
  • 종이에 적힌 수 $X$를 지우고, 그 자리에 $X-P$를 적는다.
  • Bob의 차례가 되어 같은 과정을 반복한다.
  • 자신의 차례에 종이에 0 또는 1이 적혀 있으면 그 사람이 진다. 즉 $X-P$가 0 또는 1이 되면 $P$를 고른 쪽이 이긴다.

예를 들어 $N = 8$이라면, Alice가 자신의 처음 차례에 7을 고르면 이긴다.

$N = 10$이라면 Alice가 고를 수 있는 소수는 2, 3, 5, 7이다. 2를 고르면 Bob이 8을 받고 7을 골라 이긴다. 3을 고르면 Bob이 7을 받고 7을 골라 이긴다. 5를 고르면 Bob이 5를 받고 5를 골라 이긴다. 7을 고르면 Bob이 3을 받고 3을 골라 이긴다. 따라서 Bob이 최선을 다하면 $N = 10$일 때 Alice는 이길 수 없다. 두 사람은 언제나 최선을 다해 플레이한다고 가정한다.

Bob은 $A$와 $k$를 바탕으로 $x$를 골라 $k$번의 게임에서 자신의 승률을 최대화하려고 한다. 최대화하는 $x$가 여럿이면 그중 가장 작은 $x$를 찾는다. Bob을 도와주자.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어지는 각 줄에는 공백으로 구분된 $A$와 $k$가 주어진다.

각 테스트 케이스마다 공백으로 구분된 정수 두 개를 출력한다. 첫 번째 수는 $k$번의 게임 중 Bob이 최대 몇 번 이길 수 있는지를 나타낸다. 두 번째 수는 이 최댓값을 달성하는 $x$ 중 가장 작은 값이다.

• $1 \le T \le 50$
• $3 \le A \le 100000$
• $2 \le k \le A-1$