You are given a positive integer ‘n’. Your task is to find the largest prime factor of this given positive integer.

Note :

If there is no prime factor of a given integer, then print -1.

Input Format :

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first and only line of each test case contains a positive integer ‘n’.

Output Format :

For each test case, print the largest prime factor of the given positive integer in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 50
1 <= n <= 10^9

Where ‘T’ is the number of test cases and ‘n’ is the size of the array.

Time Limit: 1 sec