1049 - One is an Interesting Number:: HUST Online Judge

1049 - One is an Interesting Number

Time Limit : 1 Second

Memory Limit : 128 MB

Submission: 124

Solved: 28

Description

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). eg:2, 113,
square: The number is the second power of an integer. eg:4, 225, 1089
cube: The number is the third power of an integer. eg:8, 3375, 35937
quad: The number is the fourth power of an integer. eg:16, 50625, 1185921
sum-multiple: The number is a multiple of the sum of its digits. eg:1, 24, 100
multiple-multiple:The number is a multiple of the number made when multiplying its digits together. eg: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

hint

source