One is an Interesting Number

Introduction:

Numbers are interesting, but some are inherently more interesting than others, by various criteria. Given a collection of numbers, you are to find the most interesting ones.

A number X is more interesting than another number Y if it has more attributes than Y. For the purposes of this problem, the attributes that are interesting are:

Attribute Name	Description	Example Numbers
prime	The number is prime (not divisible by numbers other than itself and 1).	2, 113, 2^32582657 − 1
square	The number is the second power of an integer.	4, 225, 1089
cube	The number is the third power of an integer.	8, 3375, 35937
quad	The number is the fourth power of an integer.	16, 50625, 1185921
sum-multiple	The number is a multiple of the sum of its digits.	1, 24, 100
multiple-multiple	The number is a multiple of the number made when multiplying its digits together.	1, 24, 315

Note that 0 has no multiples other than itself, and 1 is not prime.

In addition to the above attributes, there are also those which depend on the other numbers in a given collection:

Attribute Name	Description
factor	The number is a factor of another number in the collection.
multiple	The number is a multiple of another number in the collection.
other-square	The number is the second power of another number in the collection.
other-cube	The number is the third power of another number in the collection.
other-quad	The number is the fourth power of another number in the collection.
other-sum-multiple	The number is a multiple of the sum of digits of another number in the collection.
other-multiple-multiple	The number is a multiple of the number made when multiplying the digits of another number in the collection together.

This makes for a total of thirteen possible attributes. Note that meeting the criteria for a particular attribute in multiple ways (1 is the factor of all other numbers, for example) still only counts as a single instance of an attribute.

Given a collection of numbers, you are to determine which numbers in that collection are most interesting.

Input:

Input to this problem will begin with a line containing a single integer N (1 ≤ N ≤ 100) indicating the number of data sets. Each data set consists of the following components:

A line containing a single integer M (1 ≤ M ≤ 100) indicating how many numbers are in the collection;
A series of M lines, each with a single integer X (1 ≤ X ≤ 1000000). There will be no duplicate integers X within the same data set.

Output:

For each data set in the input, output the heading "DATA SET #k" where k is 1 for the first data set, 2 for the second, and so on. For each data set, print the number or numbers that are most interesting in the collection. If more than one number ties for "most interesting," print them in ascending order, one to a line.

Sample Input:

Sample Output:

DATA SET #1
1
DATA SET #2
4