Hide

Problem C
Down To Factor

Languages en is
/problems/hi.downtofactor/file/statement/en/img-0001.png
Image taken from commons.wikimedia.org
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