2008 South Central USA Regional Programming Contest

## 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, 232582657 − 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:

2
2
1
100
3
2
3
4

Sample Output:

DATA SET #1
1
DATA SET #2
4