1 import java.io.*;
    2 import java.util.*;
    3 /**
    4  * Solution to Flooring Tiles
    5  *
    6  * @author vanb
    7  */
    8 public class solution1
    9   {
   10     public Scanner sc;
   11     public PrintStream ps;
   12 
   13     public static final long biggest = 1000000000000000L;
   14     public static final long biggestprint = 1000000L;
   15 
   16     public long primepowers[][] = new long[100][1000];
   17     public boolean isprime[] = new boolean[100];
   18 
   19     /**
   20      * Find the minimum number that has n factors, with p as its smallest prime factor.
   21      *
   22      * @param n Number of desired factors
   23      * @param p Smallest prime
   24      * @param square Are we looking for a perfect square?
   25      * @param most The must of a prime we can use.
   26      * @return The minimum, as stated.
   27      */
   28     public long minimum( int n, int p, boolean square, int most )
   29     {
   30       long result = biggest;
   31 
   32       if ( n==1 )
   33         {
   34           result = 1L;
   35         }
   36       else
   37         {
   38           // Find the next highest prime
   39           int nextp = p;
   40           for ( ++nextp; !isprime[nextp]; ++nextp );
   41 
   42           // Find factors of n
   43           for ( int i=1; i<n; i++ ) if ( n%i==0 )
   44               {
   45                 int f = n/i;
   46                 if ( f-1<=most && (!square || f%2==1) )
   47                   {
   48                     long possibility = primepowers[p][f-1];
   49 
   50                     // Check and make sure the prime power isn't too big
   51                     if ( possibility!=0 )
   52                       {
   53                         long min = minimum( i, nextp, square, f-1 );
   54 
   55                         // Only multiply if it won't overflow.
   56                         if ( min < biggest/possibility )
   57                           {
   58                             possibility *= min ;
   59                             if ( possibility<result ) result = possibility;
   60                           }
   61                       }
   62                   }
   63               }
   64         }
   65       return result;
   66     }
   67 
   68     /**
   69      * Driver.
   70      * @throws Exception
   71      */
   72     public void doit() throws Exception
   73       {
   74         sc = new Scanner( System.in ); //sc = new Scanner( new File( "flooringtiles.judge" ) );
   75         ps = System.out; //new PrintStream( new FileOutputStream( "flooringtiles.solution" ) );
   76 
   77         // Use the Sieve of Eratosthanes to discover primes
   78         Arrays.fill( isprime, true );
   79         isprime[0] = isprime[1] = false;
   80 
   81         for ( int i=2; i<isprime.length; i++ ) if ( isprime[i] )
   82             {
   83               // This is the sieve of Eratosthanes. If i is prime,
   84               // then mark 2*i, 3*i, 4*i, etc. as not prime.
   85               for ( int j=i+i; j<isprime.length; j+=i ) isprime[j] = false;
   86 
   87               // We'll also compute prime powers here, to save time later.
   88               // primepowers[i][x] will be i^x if i is prime, null otherwise.
   89               Arrays.fill( primepowers[i], 0L );
   90               primepowers[i][0] = 1L;
   91               for ( int j=1; j<primepowers[i].length; j++ )
   92                 {
   93                   primepowers[i][j] = primepowers[i][j-1] * i;
   94 
   95                   // Use a negative as an indication of overflow
   96                   if ( primepowers[i][j] > biggest )
   97                     {
   98                       primepowers[i][j] = 0L;
   99                       break;
  100                     }
  101                 }
  102             }
  103 
  104         int num_cases = sc.nextInt();
  105         for ( int i=0; i<num_cases; i++ )
  106           {
  107             int n = sc.nextInt();
  108             if ( n==0 ) break;
  109 
  110             // If you can form n unique rectangles with x little boxes, then there
  111             // must be n factors of x less than or equal to its square root. So, there are
  112             // two cases - either it has 2n total factors, or it's a perfect square
  113             // and it has 2n-1 factors. We'll compute both, and take the smaller of the two.
  114             long answer = Math.min( minimum( n+n, 2, false, n+n ), minimum( n+n-1, 2, true, n+n ) );
  115             if ( answer > biggestprint )
  116               ps.println( "Too big" );
  117             else
  118               ps.println( answer );
  119           }
  120       }
  121 
  122     public static void main( String[] args ) throws Exception
  123       {
  124         new solution1().doit();
  125       }
  126   }
  127