```    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;
17     public boolean isprime[] = new boolean;
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 = isprime = 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] = 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