# Maximum Factors Problem solution codechef

## Maximum Factors Problem solution codechef

You are given an integer NN. Let KK be a divisor of NN of your choice such that K>1K>1, and let M=NKM=NK. You need to find the smallest KK such that MM has as many divisors as possible.

NoteUU is a divisor of VV if VV is divisible by UU.

### Input Format

• The first line of the input contains an integer TT – the number of test cases. The test cases then follow.
• The only line of each test case contains an integer NN.

### Output Format

For each test case, output in a single line minimum value of KK such that MM has as many divisors as possible.

### Constraints

• 1T30001≤T≤3000
• 2N1092≤N≤109

### Sample Input 1

3
3
4
6


### Sample Output 1

3
2
2


### Explanation

• Test case 11: The only possible value for KK is 33, and that is the answer.
• Test case 22: There are two cases:
• K=2K=2. Then M=42=2M=42=2, which has 22 divisors (11 and 22).
• K=4K=4. Then M=44=1M=44=1, which has 11 divisor (11).