1 Is an Interesting Number

Every number is interesting in its own way, but once we fix some criteria, we can say that certain numbers are more interesting than others. If a number $X$ satisfies more "properties" than a number $Y$, we say that $X$ is more "interesting" than $Y$.

Given a set of numbers, we must find the most interesting number in it.

First, the properties that can be judged from a number by itself are:

• 1. Prime: a number divisible by no numbers other than $1$ and itself. (e.g. $2$, $113$)
• 2. Square: the square of some integer. (e.g. $4$, $225$, $1089$)
• 3. Cube: the cube of some integer. (e.g. $8$, $3375$, $35937$)
• 4. Fourth power: the fourth power of some integer. (e.g. $16$, $50625$, $1185921$)
• 5. Digit-sum multiple: a multiple of the sum of its own digits. (e.g. $1$, $24$, $100$)
• 6. Digit-product multiple: a multiple of the product of its own digits. (e.g. $1$, $24$, $315$)

Note that $1$ is not prime, and that the only multiple of $0$ is $0$ (so if any digit is $0$, the digit product is $0$ and the number cannot be a digit-product multiple).

Next, some properties depend on the given set. Below, "some number" always means a number that belongs to the set and is not the number being judged.

• 7. Divisor: a divisor of some number in the set.
• 8. Multiple: a multiple of some number in the set.
• 9. Set-square: the square of some number in the set.
• 10. Set-cube: the cube of some number in the set.
• 11. Set-fourth-power: the fourth power of some number in the set.
• 12. Set-digit-sum multiple: a multiple of the digit sum of some number in the set.
• 13. Set-digit-product multiple: a multiple of the digit product of some number in the set.

Note that "some number" is never the number itself. For example, $1$ is the fourth power of $1$, but because that is the number itself, it does not count toward the set-fourth-power property.

Among these $13$ properties, the numbers that satisfy the greatest count are called the "most interesting numbers". Print every most interesting number in the set; if there are several, print all of them in ascending order.

The first line contains the number of test cases $T$ ($1 \le T \le 100$).

Each test case is given as follows:

• First, the size of the set $N$ ($1 \le N \le 100$) is given on its own line.
• Then $N$ lines follow, each containing one integer $X$ ($1 \le X \le 1,000,000$). All numbers in the set are distinct.

For each test case, first print DATA SET #k, where $k$ is the test case number (starting from $1$).

Then, on the following lines, print the most interesting numbers of that set in ascending order, one per line.