Limits 1s, 512 MB

Aladdin is a fictional character and the titular protagonist of Walt Disney Pictures' 31st animated feature film Aladdin (1992) based on Aladdin, a folk tale of Middle Eastern origin. When Aladdin is initially introduced, he is eighteen years old. He never received a formal education, and has only learned by living on the streets of Agrabah. He has to steal food in the local market in order to survive. He was born to Cassim and his wife. When Aladdin was only an infant, his father left him and his mother in order to find a better life for his family.

Once, you were playing with Aladdin. He gave you a task. He gave you an array/list like this: {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97} . He gave you a non-negative integer and you have to tell which of the above numbers fully divide(s) this given non-negative number. You have to print the indexes of number(s) (which divide(s) the given non-negative number) of the above array/list. Suppose, this array/list is 1 indexed.

Input

There are several test cases. The first line of input contains a positive integer $T$ ($ 1 \le T \le 1000 $), which denotes the number of test cases. In each line of next T lines, there will be given a non-negative integer number $X$ ($ 0 \le X \le 10^{1000} $).

Output

Output will contain $T$ lines. In each line, you have to print indexes of the given array/list elements (the array elements which divide the given non-negative number of the consecutive case). If there are more than one such indexes, print the indexes in ascending order separating by space. Don't print any extra space. If none of the array elements divides the non-negative number, print $\texttt{-1}$.

Sample

InputOutput
5
10201
100000
12
750
0
-1
1 3
1 2
1 2 3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

10201 isn't divided by any number of the array/list. So, ans. is -1.
100000 is divided by 2 & 5. For this index is 1 & 3.
0 is divided by all the numbers of the array.


Submit

Login to submit.

Statistics

77% Solution Ratio
iammarajulEarliest, May '20
tuhin107494Fastest, 0.0s
YouKnowWhoLightest, 131 kB
steinumShortest, 234B
Toph uses cookies. By continuing you agree to our Cookie Policy.