#1981 기식왕 류기식2

10  1 s   128 MB  

Description

 

류주의 기숙사식당 습격 사건이 이후 기숙사 식당의 보안은 더욱 강력해졌다. 게다가 기숙사 식당은 보복성 식단으로 치킨마요 덮밥을 일주일 고정메뉴로 만들기 시작한다.
“이건 치킨에 대한 모독이다.”
이번에도 기숙사 식단의 극악무도한 횡포인 치킨마요 덮밥 고정메뉴를 저지하기 위하여 다시 한번 류주는 기숙사 식당에 침투하여 식단을 조작하고자 한다. 하지만 강화된 보안시스템으로
인하여 류주는 발만 동동 구르고 있다.
하지만 이번에도 치킨의 정의를 지키는 APC(Association of Professional Chicken)의 도움으로 새로운 보안 시스템의 정보를 입수한 류주.
보안시스템의 비밀번호는 소인수 분해를 했을 때 같은 소수를 2 개 이상 포함하지 않는 N 번째로 큰 수였다.
류주를 도와줄 프로그램을 작성하여 기숙사 식당의 음모를 물리치자.
· 0 번째 수는 1 로 정의한다.
· 소인수 분해는 어떤 수를 소수의 곱으로써 나타낸 것이다.
· 소수는 1 과 자기자신 외에는 나누어 떨어지지 않는 숫자를 말한다.
· 예를 들어 6 = 2 * 3 이므로 소인수 분해를 했을 때 2 와 3 의 곱으로 만들어진다. 60 = 2 * 2 * 3 * 5 로 2 가 두 번 들어간다.

Input

 

첫 번째 줄에는 테스트케이스의 수 T 가 입력된다. (1 <= T <= 20)
각 테스트 케이스에는 N(0 <= N <= 100000)이 한 줄에 입력된다.

Output

각 테스트 케이스에 대해서 한 줄에 N 번째 숫자를 출력한다.

Sample Input

Sample Output

3
0
10000
50000
1
16447
82258

Source

Ajou Programming Contest, Division 1