양치기와 공학자

웨스트모얼랜드는 잔잔한 강과 거친 황야, 그리고 양 떼를 치는 양치기들이 사는 평화로운 나라입니다. 마을의 양 시장으로 가려면 양치기는 강을 건너야 합니다. 폭우가 내린 뒤로 강을 걸어서 건너기가 너무 위험해지자, 공학자들이 다리를 놓았고 다리를 건너는 모든 양치기에게서 양으로 통행료를 받을 수 있게 되었습니다.

과도한 통행료를 막기 위해 왕은 다음과 같이 정했습니다. 양치기가 양 몇 마리를 데리고 다리를 건널 때 공학자가 통행료를 받는다면,

1. 양치기가 갖는 양의 수는 공학자가 가져가는 양의 수보다 엄격히 많아야 하고,
2. 양치기가 갖는 양의 수는 공학자가 가져가는 양의 수의 정수 배여야 합니다.

공학자는 언제나 규칙이 허용하는 가장 큰 통행료를 받습니다. 즉 양치기가 다리에 양 $n$마리를 데리고 와 통행료로 $t$마리를 낸다면, 남는 $n - t$마리는 어떤 정수 $k \ge 2$에 대해 $n - t = k\cdot t$를 만족해야 합니다. 다시 말해 $n = (k+1),t$이고 $k+1 \ge 3$입니다. 이 조건을 만족하는 통행료 가운데 공학자는 가장 큰 $t$를 가져갑니다. 유효한 통행료가 존재하지 않으면(예를 들어 양이 한두 마리뿐일 때) 그 다리는 무료로 건넙니다.

양치기는 다리를 건너기 전에 이웃 양치기에게 양을 나눠 주어 양의 수를 최대 통행료가 더 작은 수로 낮추는 방식으로 대응합니다. 예를 들어 마을에서 다리 네 개만큼 떨어진 곳에서 양 $40$마리를 팔아야 하는 양치기는 $47$마리로 출발할 수 있습니다.

• 다리 1: $47$마리, 통행료 $1$, 남는 수 $46$.
• 다리 2: $46$마리, 통행료 $2$, 남는 수 $44$.
• 다리 3: $44$마리에 대한 통행료 $11$을 내는 대신, 양 $1$마리를 나눠 주고 $43$마리로 건너 통행료 $1$, 남는 수 $42$.
• 다리 4: 양 $1$마리를 나눠 주고 $41$마리로 건너 통행료 $1$, 남는 수 $40$.

이렇게 하면 정확히 $40$마리를 데리고 마을에 들어가며, 더 적은 수로 출발해서는 이 결과를 얻을 수 없습니다.

양치기가 마을로 데려가려는 양의 수 $s$와 가는 길에 있는 다리의 수 $b$가 주어질 때, 여행을 시작할 때 필요한 최소 양의 수를 구하세요. 최적의 계획이 때로는 필요한 것보다 더 많은 양을 데리고 마을에 들어가게 만들 수도 있습니다.

첫 줄에 테스트 케이스의 수 $T$가 주어집니다.

각 테스트 케이스는 두 정수 $s$와 $b$로 이루어진 한 줄입니다.

• $s$ ($0 < s \le 10^6$) — 마을에 들여보내야 하는 양의 수,
• $b$ ($0 \le b \le 1000$) — 건너야 하는 다리의 수.

각 테스트 케이스마다, 양치기가 출발할 때 필요한 최소 양의 수를 한 줄에 정수 하나로 출력합니다.