学长曾感受到一份与众不同的快乐，他想把这份快乐传递出去，这份快乐被随机分成了x份（x>=2），但是由于学长有强迫症，他希望分开的每一份快乐都是一个质数，且所有快乐的和与原来相同，学长想知道他最多能传递多少份快乐（即求x的最大值）
第一行一个整数 T (1≤T≤10^5)，表示测试用例的数量。
对于每组测试用例，输入一行一个整数 s (1≤s≤10^6)表示这份快乐的初始值。
对于每组测试用例，输出一行一个整数，如果x有解，则输出x，否则输出−1。
2
5
4
2
2
在第一组测试用例中，快乐最多可以被分为2份，蕴含的力量分为2,3。
在第二组测试用例中，快乐最多可以被分为 2 份，蕴含的力量分别为 2,2。