시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB2421416753.175%

문제

행운 수(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 …
  5. 1 3 7 9 13 15 19 21 25 …
  6. 1 3 7 9 13 15 19 21 25 …
  7. 1 3 7 9 13 15 21 25 …
  8. 1 3 7 9 13 15 21 25 …

자연수 n이 주어지면 n이 행운 수인지 아닌지 알아보자.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. (1 ≤ T ≤ 10,000 = 104)

각 테스트 케이스는 한 줄로 이루어져 있으며, 자연수 n이 주어진다. (1 ≤ n ≤ 1,000,000 = 106)

출력

각 테스트 케이스마다 n이 행운 수이면 “lucky”를, n이 행운 수가 아니면 “unlucky”를 큰따옴표 없이 출력한다.

예제 입력 1

10
1
2
3
4
5
6
7
8
9
10

예제 출력 1

lucky
unlucky
lucky
unlucky
unlucky
unlucky
lucky
unlucky
lucky
unlucky

예제 입력 2

7
43
29
1247
8481
73731
393939
123456

예제 출력 2

lucky
unlucky
unlucky
unlucky
lucky
lucky
unlucky

출처