Tobby the boston terrier is trying to escape from the pyramid of the egyptian pharaoh. To escape, Tobby has to solve a riddle that asks him to factor a list of large integers. The fastest way Tobby knows of factoring integers is iterating over all primes up to the square root of the target number, checking for prime factors. The problem is that in this case the number of primes to check would be very large, so he cannot use that method. Can you help him solve the riddle? Input Input begins with an integer t (1 ≤ t ≤ 100), the number of integers to factor, followed by t lines, each line contains an integer n (2 ≤ n ≤ 263 − 1). Output For each test case, you should print a single line containing the prime factors of n sorted in increasing order. Note that in case of repeated prime factors, such factors have to be printed several times. Sample Input 3 2 91 40 Sample Output 2 7 13 2225