Problem C
Down To Factor

While most members of ICPS are outside in the rain trying to make sure Eyleifur doesn’t break his neck, Benni is inside on his phone. He is perusing his SystemD app, trying to find something to do next weekend. He is trying to find a gal who will be willing to watch Nettis with him that weekend. As Benni’s favourite number is $6$, he only wants to contact girls with a phone number with exactly $6$ divisors. He would gladly accept your help in filtering out all the phone numbers that don’t have exactly $6$ divisors.

Input

The first line in the input contains one positive integer $k$ satisfying $1 \leq k \leq 10^3$. The following $k$ lines contain the phone numbers Benni has collected. Each phone number is an $18$ digit number, possibly with leading zeroes.

Output

The output should contain the phone numbers Benni is interested in, each on a separate line, in the same order as they appear in the input.

Sample Input 1	Sample Output 1
5 000000000000000001 000000000000000016 000000000000000169 000000000123456789 999999874000003969	000000000000000169 999999874000003969