1. 
/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10
* Problem: 11476 - Factorizing Large Integers
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=26&page=show_problem&problem=2471
*
* @author Felix Dietrich
* @version 1.0, 07/01/2010
*
* Method : pollard's rho algorithm
* Status : WA :((
* Runtime:
*/


import java.util.*;
import java.lang.*;

class Main
{
interface Func<T,U>
{
U execute(T... arguments);
}

public static long gcd(long a, long b)
{
if(b == 0)
return a;
return gcd(b, (long)(a-b*Math.floor((double)a/b)));
}

public static long f(long a, long b)
{
return (a*a+3)%b;
}

public static long pollardRho(long n)
{
long x=2, y=2, d=1, z=0;

while(d==1)
{
z=1;
for(int i=0; i<50;i++)
{
x = f(x,n);
y = f(f(y,n),n);
z = (z*Math.abs(x-y)) % n;
}
d = gcd(z,n);
}

if(d==n)
return -1;
else
return d;
}

// Calculate all prime numbers in the range 1 to MAX_PRIME
// using the sieve of Eratosthenes.
// numbers in the "numbers" array that are not prime are are set to -1.
static final int MAX_CALCULATED_PRIME = 1048576;
static int[] numbers = new int[MAX_CALCULATED_PRIME+5];
static List<Integer> primes = new ArrayList<Integer>();
private static void generateSomePrimes()
{
numbers[0] = -1;
numbers[1] = -1;
for (int i = 2; i <= MAX_CALCULATED_PRIME+1; i++)
{
if (numbers[i] >= 0)
{
numbers[i] = i;
primes.add(i);
for (int k = 2; k * i <= MAX_CALCULATED_PRIME+1; k++)
{
numbers[k * i] = -1;
}
}
}
}

public static List<Long> findPrimes(long n)
{
List<Long> result = new ArrayList<Long>();
long rhoResult;
Func<Long,Long> f = new Func<Long,Long>()
{
public Long execute(Long... x)
{
return (x[0]*x[0]+10)%x[1];
}
};

while(n > 1)
{
// if we reached the small numbers range, we can use the precomputed primes
if(n < MAX_CALCULATED_PRIME)
{
for(long p: primes)
{
while(n % p == 0)
{
result.add(p);
n /= p;
}
if(n < 2)
break;
}
}
else
{
rhoResult = pollardRho(n);
if(rhoResult == -1)
{
result.add(n);
n = 1;
}
else
{
result.add(rhoResult);
n /= rhoResult;
}
}
}
return result;
}

public static String format(List<Long> nlist)
{
StringBuilder sb = new StringBuilder();
Collections.sort(nlist);
int exp = 1;
long last = 0;
for(long n : nlist)
{
if(last == n)
exp++;
else
{
if(last == 0)
last = n;
else
{
sb.append(last);
if(exp > 1)
sb.append("^"+exp);
sb.append(" * ");
}
exp = 1;
}
last = n;
}
if(last != 0)
{
sb.append(last);
if(exp > 1)
sb.append("^"+exp);
}
else
{
if(sb.length() > 2)
{
sb.deleteCharAt(sb.length()-1);
sb.deleteCharAt(sb.length()-1);
}
}

return sb.toString();
}

public static void main(String... args)
{
Scanner sc = new Scanner(System.in);

generateSomePrimes();

long input;
long count = sc.nextInt();
long start = 1000000000000000l;//14

long millis = System.currentTimeMillis();

while(count > 0)
{
input = start++;//sc.nextLong();
System.out.print(input+" = ");
System.out.print(format(findPrimes(input)));

System.out.println();
count --;
}

System.out.println("Done in "+(System.currentTimeMillis()-millis)/1000+" seconds.");
}
}