学长曾感受到一份与众不同的快乐，他想把这份快乐传递出去，这份快乐被随机分成了x份（x>=2），但是由于学长有强迫症，他希望分开的每一份快乐都是一个质数，且所有快乐的和与原来相同，学长想知道他最多能传递多少份快乐（即求x的最大值）

第一行一个整数 T  (1≤T≤10^5)，表示测试用例的数量。

对于每组测试用例，输入一行一个整数 s  (1≤s≤10^6)表示这份快乐的初始值。

对于每组测试用例，输出一行一个整数，如果x有解，则输出x，否则输出−1。