#include <iostream>
#include <sstream>
#include <string>
#include <vector>

#include <math.h>

using namespace std;

/* Values smaller than EPSILON are considered zero to avoid round off errors */
#define EPSILON 0.0000001

/* Macro returning the number of elements in a statically initialized array */
#define countof(x) ( sizeof(x) / sizeof((x)[0]) )

/* Holds information about a single number X form the data set */
typedef struct {
    int value;    /* The numerical value of the number itself */
    int sum;      /* The sum of this number's digits */
    int mul;      /* The multiplication together of this number's digits */
    int square;   /* The integer square root */
    int cube;     /* The integer cube root */
    int quad;     /* The integer quad root */
    int interest; /* The number of different attributes this number posseses */
} number_t;

/* A vector holding all the numbers for a given data set */
typedef vector<number_t> data_t;

/* Numbers are sorted by most interesting and then ascending by values */
inline bool operator<(number_t const &a, number_t const &b)
{
    if(a.interest == b.interest) {
        return a.value < b.value;
    }
    else {
        return a.interest > b.interest;
    }
}

/* SANITY CHECK: The equality operator is used to check for duplicate numbers */
inline bool operator==(number_t const &a, number_t const &b)
{
    return a.value == b.value;
}

/*
 * If integer "power" is the "n"th power of some integer, then return the
 * "n"th integer root. If the root is not an integer, return -1. Note that
 * due to the inherent round-off errors present in floating point numbers, it
 * is not possible to directly compare a double and an integer for equality.
 */
int root(int power, int n)
{
    /* Compute the floating point "n"th root of "power" */
    double decimal = pow(power, 1.0 / n);

    /* Round floating point root to neareast integer */
    int integer = (int) (decimal + 0.5);
    
    /* Check if rounded integer and original value are "close enough" */      
    return fabs(decimal - integer) < EPSILON ? integer : -1;
}

/* Check if number "haystack" is a multiple of number "needle" */
bool ismultiple(int haystack, int needle)
{
    /* A zero is a multiple only of itself */
    if(haystack == 0 || needle == 0) {
        return (haystack == 0 && needle == 0) ? true : false;
    }
    
    /* If haystack is a multiple of needle, then needle divides it evenly */
    return (haystack % needle) == 0 ? true : false;
}

/*
 * Execute the attribute predicate "test(number, other[i])" for every number
 * in "other" except for the "other[i]" equal to "number". If the predicate
 * returns non -1 for any number in "other", then return this result.
 * Otherwise return -1 indicating that no numbers in "other" matched the
 * attribute predicate.
 */
int forother(number_t &number, data_t &other, int (*test)(number_t &, number_t &))
{
    for(int i = 0; i < other.size(); i++) {
        if(number.value != other[i].value) {
            int result = test(number, other[i]);
            if(result != -1) {
                return result;
            }
        }
    }
    return -1;
}

/*
 * Attribute: return "number" if "number" is prime and -1 otherwise. Two
 * observations about numbers can be used to speed up this test. First, any
 * number divisible by a multiple of 2 is also divisible by 2 itself.
 * Therefore we only need to test if a number is divisible by odd numbers.
 * Second, if a number has any factors, one of those factors must be less than
 * or equal to the square root of the number. Therefore we only need to test
 * divisibility by numbers less than or equal the sqrt of the potential prime.
 */
int prime(number_t &number)
{
    /* The numbers 0 and 1 are never prime */
    if(number.value == 1 || number.value == 0) {
        return -1;
    }
    
    /* The number 2 is prime */
    if(number.value == 2) {
        return number.value;
    }
    
    /* An even number cannot be prime since it is divisible by 2 */
    if( !(number.value % 2) ) {
        return -1;
    }

    /* Find an integer less than or equal to the number's square root */
    int limit = (int) pow(number.value, 0.5);

    /* Assume the number is prime until proven otherwise */
    bool prime = true;

    /* Check if divisible by any odd factors <= to the sqrt of number.value */
    for(int i = 3; i <= limit; i += 2) {
        if( !(number.value % i) ) {
            prime = false;
            break;
        }
    }

    return prime ? number.value : -1;
}

/* Attribute: check if "number" is a second power of any integer */
int square(number_t &number)
{
    return number.square;
}

/* Attribute: check if "number" is a third power of any integer */
int cube(number_t &number)
{
    return number.cube;
}

/* Attribute: check if "number" is a fourth power of any integer */
int quad(number_t &number)
{
    return number.quad;
}

/* Attribute: check if "number" is a multiple of the digit sum */
int mul_sum(number_t &number)
{
    return ismultiple(number.value, number.sum) ? number.sum : -1;
}

/* Attribute: check if "number" is a multiple of the digit multiple */
int mul_mul(number_t &number)
{
    return ismultiple(number.value, number.mul) ? number.mul : -1;
}

/* Attribute: check if "number" is a factor of the number "other" */
int factor(number_t &number, number_t &other)
{
    return ismultiple(other.value, number.value) ? other.value : -1;
}

/* Attribute: check if "number" is a multiple of the number "other" */
int multiple(number_t &number, number_t &other)
{
    return ismultiple(number.value, other.value) ? other.value : -1;
}

/* Attribute: check if "number" is the second power of number "other" */
int other_square(number_t &number, number_t &other)
{
    return number.square == other.value ? other.value : -1;
}

/* Attribute: check if "number" is the third power of number "other" */
int other_cube(number_t &number, number_t &other)
{
    return number.cube == other.value ? other.value : -1;
}

/* Attribute: check if "number" is the fourth power of number "other" */
int other_quad(number_t &number, number_t &other)
{
    return number.quad == other.value ? other.value : -1;
}

/* Attribute: check if "number" is a multiple of the digit sum of "other" */
int other_sum_mul(number_t &number, number_t &other)
{
    return ismultiple(number.value, other.sum) ? other.sum : -1;
}

/* Attribute: check if "number" is a multiple of the digit multiple of "other" */
int other_mul_mul(number_t &number, number_t &other)
{
    return ismultiple(number.value, other.mul) ? other.mul : -1;
}

/*
 * Array of predicate functions for each of the attributes. Each predicate
 * functions returns -1 to indicate no attribute match. Any other value
 * indicates a match and if DEBUG mode is used, this value also gets printed
 * to stderr.
 */
int (* const individual_pred[])(number_t &) = {
    prime, square, cube, quad, mul_sum, mul_mul
};
int (* const group_pred[])(number_t &, number_t &) = {
    factor, multiple, other_square, other_cube, other_quad,
    other_sum_mul,  other_mul_mul
};

#ifdef DEBUG
/* DEBUG ONLY: Array of attribute names; order must match "pred" array */
char const * const individual_name[] = {
    "prime", "square", "cube", "quad", "mul_sum", "mul_mul"
};
char const * const group_name[] = {
    "factor", "multiple", "other_square", "other_cube", "other_quad",
    "other_sum_mul", "other_mul_mul"
};
#endif

/* Main body of program */
void process(void)
{
    int data_num, data_idx;
    
    /* Read how many data sets to process */
    cin >> data_num;
    
    /* Process each data set separately */
    for(data_idx = 0; data_idx < data_num; data_idx++) {
        int value_num, value_idx;
        data_t data;
        
        /* Read how many input numbers are present in data set */
        cin >> value_num;
        
        /* Read in each of the interesting numbers from the input */
        for(value_idx = 0; value_idx < value_num; value_idx++) {
            number_t number;
            ostringstream stream;
            string text;
            
            /* Read in raw integer */
            cin >> number.value;
            
            /* SANITY CHECK: Check for duplicate numbers in the data set */
            if(find(data.begin(), data.end(), number) != data.end()) {
                cerr << "Duplicate number: " << number.value << endl;
                throw;
            }

            /* Convert number to a string to extract individual digits */
            stream << number.value;
            text = stream.str();
            
            /* Compute the sum and multiple of the number's individual digits */
            number.sum = 0;
            number.mul = 1;
            for(int i = 0; i < text.size(); i++) {
                number.sum += text[i] - '0';
                number.mul *= text[i] - '0';
            }
            
            /* Check if the square, cubic, and quad roots are integers */
            number.square = root(number.value, 2);
            number.cube = root(number.value, 3);
            number.quad = root(number.value, 4);
            
            /* Add the number to the input data list */
            data.push_back(number);
        }

        /* Print out data set header */
        cout << "DATA SET #" << data_idx + 1 << endl;        
#ifdef DEBUG
        cerr << "DATA SET #" << data_idx + 1 << endl;        
#endif        
        /*
         * Count how many attribute predicates hold true for number.
         * DEBUG ONLY: For each matching attribute, print the attributes name
         * along with any attribute specific data returned by the predicate.
         */
        data_t::iterator number;
        for(number = data.begin(); number != data.end(); ++number) {            
            number->interest = 0;
#ifdef DEBUG
            cerr << number->value << ":";
#endif
            /* Test for individual attributes */
            for(int i = 0; i < countof(individual_pred); i++) {
                int result = individual_pred[i](*number);
            
                if(result != -1) {
                    number->interest++;
#ifdef DEBUG
                    cerr << " " << individual_name[i] << "=" << result;
#endif
                }
            }

            /* Test for group attributes */
            for(int i = 0; i < countof(group_pred); i++) {
                int result = forother(*number, data, group_pred[i]);
            
                if(result != -1) {
                    number->interest++;
#ifdef DEBUG
                    cerr << " " << group_name[i] << "=" << result;
#endif
                }
            }

#ifdef DEBUG
            cerr << endl;
#endif            
        }
        
        /* Sort the numbers by most interesting and then by values */
        sort(data.begin(), data.end());
        
        /* Print the N most interesting (in case of ties) numbers */
        int interest = data[0].interest;
        for(int i = 0; i < data.size(); i++) {
            if(interest == data[i].interest) {
                cout << data[i].value << endl;
#ifdef DEBUG
                cerr << data[i].value << endl;
#endif            
            }
        }
    }
}

/* Run program and print out any exceptions that occur */
int main(void)
{
    /* Throw exceptions on failed data extraction in >> operator */
    cin.exceptions(ios::failbit);
    
    /* Run main body of code */
    try {
        process();
    }
    
    /* Catch unexpected EOF or bad input data */
    catch(ios::failure const &e) {
        cerr << "Unexpected EOF or data type mismatch on input" << endl;
    }

    return 0;
}