28159번 - K번째 행운 수

문제

행운 수(Lucky numbers)는 에라토스테네스의 체와 비슷한 방법으로 만들어지는 자연수의 부분집합 또는 그 부분집합의 원소를 말한다.

행운 수의 집합은 다음과 같은 과정을 통해 구성할 수 있다.

1. 홀수 자연수의 목록을 만든다.
2. 목록에 속한 수 중 1보다 크면서 선택한 적이 없는 수 중에서 가장 작은 수를 선택한다.
3. 2.에서 선택한 자연수를 k라고 할 때, 목록에서 오름차순으로 i×k (i ≥ 1) 번째에 해당하는 모든 자연수를 지운다.
4. 2.로 돌아간다.

다음은 위 과정의 일부를 수행하는 예시이다.

1. 1 3 5 7 9 11 13 15 17 19 21 23 25 …
2. 1 3 5 7 9 11 13 15 17 19 21 23 25 …
3. 1 3 (削除) 5 (削除ここまで) 7 9 (削除) 11 (削除ここまで) 13 15 (削除) 17 (削除ここまで) 19 21 (削除) 23 (削除ここまで) 25 …
4. 1 3 7 9 13 15 19 21 25 …
2. 1 3 7 9 13 15 19 21 25 …
3. 1 3 7 9 13 15 (削除) 19 (削除ここまで) 21 25 …
4. 1 3 7 9 13 15 21 25 …
2. 1 3 7 9 13 15 21 25 …
3. …

자연수 K가 주어지면 K번째 행운 수를 알아보자.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. (1 ≤ T ≤ 5)

각 테스트 케이스는 한 줄로 이루어져 있으며, 자연수 K가 주어진다. (1 ≤ K ≤ 3,000,000 = 3 × 10⁶)

출력

각 테스트 케이스마다 K번째 행운 수를 출력한다.

제한

힌트