1은 흥미로운 숫자

물론 모든 숫자들은 흥미롭지만, 기준에 따라 어떠한 숫자들은 다른 숫자들보다 더 흥미롭기도 하다. 숫자 X가 숫자 Y보다 더 많은 "특징"을 가진다면 우리는 이를 "흥미롭다" 고 한다.

우리는 수 집합이 주어졌을 때 가장 흥미로운 수를 찾아야 한다.

다음은 "흥미로운 숫자" 들의 특징이다 -

• 1. 소수 : 1과 자기 자신이 아닌 수들에게 나누어지지 않는 수. (ex : 2, 113)
• 2. 제곱수 : 어떠한 정수의 제곱수. (ex : 4, 225, 1089)
• 3. 세제곱수 : 어떠한 정수의 세제곱수. (ex : 8, 3375, 35937)
• 4. 네제곱수 : 어떠한 정수의 네제곱수. (ex : 16, 50625, 1185921)
• 5. 합배수 : 각 자리수들의 합의 배수 (ex : 1, 24, 100)
• 6. 곱배수 : 각 자리수들의 곱의 배수 (ex : 1, 24, 315)

1은 소수가 아니며, 0의 배수는 0 뿐임을 유념하여라.

또한, 주어지는 집합의 따라 수의 흥미로움을 결정하는 특징도 있다. 다음은 그러한 "흥미로운 숫자" 들의 특징이다.

• 7. 약수 : 주어지는 집합에 있는 어떠한 수의 약수.
• 8. 배수 : 주어지는 집합에 있는 어떠한 수의 배수.
• 9. 사과제곱수 : 주어지는 집합에 있는 어떠한 수의 제곱수.
• 10. 사과세제곱수 : 주어지는 집합에 있는 어떠한 수의 세제곱수.
• 11. 사과네제곱수 : 주어지는 집합에 있는 어떠한 수의 네제곱수.
• 12. 사과합배수 : 주어지는 집합에 있는 어떠한 수의 자리수들의 합의 배수.
• 13. 사과곱배수 : 주어지는 집합에 있는 어떠한 수의 자리수들의 곱의 배수.

"어떠한 수"는 자기 자신이 아님에 유의하라. 즉, 1은 자기 자신의 사과네제곱수지만, 이는 특징으로 세지 않는다.

이러한 13개의 특징이 주어졌을 때, 만족하는 특징의 개수가 가장 큰 것들을 "가장 흥미로운 수"라고 한다. 집합에서 "가장 흥미로운 수" 들을 출력하고, 만약 그러한 수가 여러개라면 오름차순으로 모두 출력하라.

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

이후 T개의 줄에 다음 수들이 주어진다 :

• 먼저 집합의 크기 N이 주어진다. (1 ≤ N ≤ 100)
• 이후 N개의 줄에 숫자 X가 주어진다. (1 ≤ X ≤ 1000000) 집합에 있는 수들은 모두 다르다.

각각의 테스트 케이스에 대해 먼저 첫 줄에 "DATA SET #k"를 출력하라. k는 테스트 케이스의 번호다.

이후 흥미로운 숫자들을 여러 줄에 걸쳐 오름차순으로 출력한다.