#!/usr/bin/env python

# Interesting Numbers solution by Phil Bordelon

import math
import os
import sys

# Debug?
DEBUG = os.getenv("DEBUG", False)

def isprime(n):

   # One isn't prime.
   if n == 1:
      return False

   # Even numbers aren't prime unless they're 2.
   if n == 2:
      return True
   elif n % 2 == 0:
      return False

   # Okay; loop through all numbers less than or equal to the square root
   # the number to find factors.  Assume primality; if it's not prime,
   # break out cos we're done.
   is_prime = True
   highest_factor = int(math.sqrt(n))
   for i in range(3, highest_factor + 1):
      if n % i == 0:
         is_prime = False
         break

   return is_prime

def ispower(n, power):

   # Find the 1/powerth root of n; this is a real number.
   real_root = math.pow(n, 1.0/power)

   # Find if its integer component is precisely n.  We do this by multiplying
   # back up.  The problem is that the int() cast may put us not at the
   # precise root, thanks to the imprecision of floating point.  So we cheat
   # by testing the number returned by int() along with the one above it;
   # since int() rounds towards zero, it could potentially be one higher.
   int_root = int(real_root)
   for test_value in (int_root, int_root + 1):
      curr_val = test_value
      for i in range(power - 1):
         curr_val *= test_value

      # Return whether or not that got us back to n.
      if curr_val == n:

         # Yup.  Return the root.
         return test_value

   # No, this is not an exact power.  Return 0.
   return 0

def digit_sum(n):

   # This simple little function calculates the sum of the digits of a number.
   curr_num = n
   sum = 0
   while curr_num >= 1:
      digit = curr_num % 10
      sum += digit
      curr_num /= 10

   return sum

def digit_mult(n):

   # This function calculates the multiplication of the digits.
   curr_num = n
   mult = 1
   while curr_num >= 1:
      digit = curr_num % 10
      mult *= digit
      curr_num /= 10

   return mult

if "__main__" == __name__:


   # Instead of duplicating work, we're going to track the data that is
   # not collection-sensitive in a dictionary for later reuse.  This
   # makes the program get more efficient, not less, across data sets.
   num_dict = {}
   dataset_count = int(sys.stdin.readline())
   for dataset_loop in range(dataset_count):

      print "DATA SET #%d" % (dataset_loop + 1)

      # Load the elements into the list.
      data_list = []
      list_len = int(sys.stdin.readline())
      for i in range(list_len):
         data_list.append(int(sys.stdin.readline()))

      # Sort the list ...
      data_list.sort()

      # Now go through them and count the pertinent elements.  Keep
      # track of the most attributes found so far.
      most_attributes = 0
      attribute_list = []

      # First pass; calculate values for numbers we haven't seen before.
      for entry in data_list:

         if entry not in num_dict:

            # All right.  We will now calculate various "static" values,
            # which do not depend on what numbers are in a given collection.
            # These are things like primality, whether the number is a
            # square, cube, or quad, and what the sum and multiplication of
            # its digits are (and whether it is a multiple of those).
            this_dict = {}
            count = 0

            # Primality doesn't need to be tracked, just counted.
            if isprime(entry):
               if DEBUG:
                  print "%d is prime!" % entry
               count += 1

            # Powers, on the other hand, are worth tracking, as we can use
            # the roots in the later per-collection phase.
            for power in (2, 3, 4):
               power_result = ispower(entry, power)
               if power_result:
                  if DEBUG:
                     print "%d is power %d of an integer!" % (entry, power)
                  count += 1
                  this_dict[power] = power_result

            # The value of the sum and multiply bits is also worth saving.
            sum = digit_sum(entry)
            if entry % sum == 0:
               if DEBUG:
                  print "%d is a multiple of its digit sum %d!" % (entry, sum)
               count += 1

            # Whether or not it's a multiple of its own sum, we need to store
            # it, so we can see if other numbers are a multiple of its sum in
            # the per-collection phase.
            this_dict["sum"] = sum

            mult = digit_mult(entry)
            if mult > 0 and entry % mult == 0:
               if DEBUG:
                  print "%d is a multiple of its digit multiple %d!" % (entry, mult)
               count += 1

            # Much like the sum above, we need to store this value for the
            # per-collection phase.
            this_dict["mult"] = mult

            # Done calculating all of the "static" values.  Store!
            this_dict["count"] = count
            num_dict[entry] = this_dict

      # Now that we've precalculated various things, loop over the values again.
      for entry in data_list:

         this_dict = num_dict[entry]

         # Start with the count of the default (non-list-dependent) attributes.
         attribute_count = this_dict["count"]
         if DEBUG:
            print "%d starts with %d attributes!" % (entry, attribute_count)

         # Other-square, -cube, and -quad are trivial.  If this number
         # /is/ a square, cube, or quad, we recorded which number it is
         # the s/c/q of.
         for attribute in (2, 3, 4):
            if attribute in this_dict and this_dict[attribute] in data_list:
               if DEBUG:
                  print "%d is the %dth power of %d!" % (entry, attribute, this_dict[attribute])
               attribute_count += 1

         # Now we have to loop through the /other/ numbers in the list for
         # the other attributes.
         for other_entry in data_list:
            if other_entry != entry:

               other_dict = num_dict[other_entry]

               # Other-sum-multiple and other-multiple-multiple are similar
               # to other-square/cube/quad, although there's a mod involved.
               for attribute in ("sum", "mult"):
                  if attribute in other_dict:
                     val = other_dict[attribute]

                     # If the value isn't zero (which only occurs for the
                     # multiplier, and is meant to be ignored), see if this
                     # is a factor of the entry.
                     if val > 0 and entry % val == 0:
                        if DEBUG:
                           print "%d is a multiple of the %s of %d!" % (entry, attribute, other_entry)
                        attribute_count += 1

               # Lastly, we have factor and multiple.
               if other_entry < entry and entry % other_entry == 0:
                  if DEBUG:
                     print "%d is a multiple of %d!" % (entry, other_entry)
                  attribute_count += 1
               elif other_entry > entry and other_entry % entry == 0:
                  if DEBUG:
                     print "%d is a factor of %d!" % (entry, other_entry)
                  attribute_count += 1

         if DEBUG:
            print "Total attribute count for %d: %d" % (entry, attribute_count)

         # Record the highest attribute count so far ...
         if attribute_count > most_attributes:
            most_attributes = attribute_count

         # ... and record /this/ attribute count.
         attribute_list.append(attribute_count)

      # Phew.  Done.  Print out the numbers with the highest attribute count;
      # there may be more than one, which is why we kept them all around.
      for i in range(list_len):
         if attribute_list[i] == most_attributes:
            print repr(data_list[i])