1은 흥미로운 숫자

모든 수는 저마다 흥미롭지만, 어떤 기준을 정하면 특정 수가 다른 수보다 더 흥미롭다고 말할 수 있다. 수 $X$가 만족하는 "특징"의 개수가 수 $Y$보다 많으면, $X$가 $Y$보다 더 "흥미롭다"고 하자.

수들의 집합이 주어질 때, 그 안에서 가장 흥미로운 수를 찾아야 한다.

먼저, 수 그 자체만으로 판단할 수 있는 특징은 다음과 같다.

• 1. 소수: $1$과 자기 자신 외의 수로는 나누어지지 않는 수. (예: $2$, $113$)
• 2. 제곱수: 어떤 정수의 제곱인 수. (예: $4$, $225$, $1089$)
• 3. 세제곱수: 어떤 정수의 세제곱인 수. (예: $8$, $3375$, $35937$)
• 4. 네제곱수: 어떤 정수의 네제곱인 수. (예: $16$, $50625$, $1185921$)
• 5. 합배수: 각 자리 숫자의 합의 배수인 수. (예: $1$, $24$, $100$)
• 6. 곱배수: 각 자리 숫자의 곱의 배수인 수. (예: $1$, $24$, $315$)

단, $1$은 소수가 아니며 $0$의 배수는 $0$뿐임에 유의하라. (어떤 자리 숫자가 $0$이면 자리 숫자들의 곱이 $0$이 되어, 그 수는 곱배수가 될 수 없다.)

다음으로, 주어진 집합에 따라 결정되는 특징이 있다. 아래에서 "어떤 수"는 항상 집합에 속하면서 판단 대상인 수 자신이 아닌 수를 뜻한다.

• 7. 약수: 집합에 있는 어떤 수의 약수인 수.
• 8. 배수: 집합에 있는 어떤 수의 배수인 수.
• 9. 사과제곱수: 집합에 있는 어떤 수의 제곱인 수.
• 10. 사과세제곱수: 집합에 있는 어떤 수의 세제곱인 수.
• 11. 사과네제곱수: 집합에 있는 어떤 수의 네제곱인 수.
• 12. 사과합배수: 집합에 있는 어떤 수의 자리 숫자 합의 배수인 수.
• 13. 사과곱배수: 집합에 있는 어떤 수의 자리 숫자 곱의 배수인 수.

"어떤 수"는 판단 대상인 수 자신이 아님에 유의하라. 예를 들어 $1$은 $1$의 네제곱이지만, 이는 자기 자신이므로 사과네제곱수 특징으로 세지 않는다.

이 $13$가지 특징 중 만족하는 개수가 가장 많은 수를 "가장 흥미로운 수"라고 한다. 집합에서 가장 흥미로운 수를 모두 찾아, 여러 개라면 오름차순으로 출력하라.

첫째 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 100$)가 주어진다.

각 테스트 케이스는 다음과 같이 주어진다.

• 먼저 집합의 크기 $N$ ($1 \le N \le 100$)이 한 줄에 주어진다.
• 이어지는 $N$개의 줄에 각각 정수 $X$ ($1 \le X \le 1\,000\,000$)가 하나씩 주어진다. 집합에 속한 수는 모두 서로 다르다.

각 테스트 케이스마다 먼저 DATA SET #k를 출력한다. 여기서 $k$는 테스트 케이스 번호(1부터 시작)이다.

그다음 줄부터, 그 집합에서 가장 흥미로운 수를 오름차순으로 한 줄에 하나씩 출력한다.