H-★★温暖的力量★★_兰州大学第一届『飞马杯』程序设计竞赛（同步赛）

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小时候， $Helen$ 曾感受到一份与众不同的温暖。那份温暖，蕴含着令人重生的力量。即便过去了很久很久，她依然无法忘却。

随着时间的流逝，这份温暖被随机分成了 $x \; (x \gt 1)$ 份。由于温暖之间的羁绊，每份温暖分到的力量都是质数，并且力量总和与原来相同。

为了重新寻回这份温暖，必须知道 $x$ 最大可能为多少。但是 $Helen$ 思考了很久，也未能如愿。

作为 $Helen$ 的好友，你不想再看到她为此忧伤。因此你需要帮助 $Helen$ 找到这个最大的 $x$ 值。

第一行一个整数 $T \; (1 \leq T \leq 10^{5})$ ，表示测试用例的数量。

对于每组测试用例，输入一行一个整数 $s \; (1 \leq s \leq 10^{6})$ ，表示这份温暖最初蕴含的力量。

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

示例1

复制

2
4
5

复制

2
2

在第一组测试用例中，温暖最多可以被分为 $2$ 份，蕴含的力量分别为 $2,2$ 。

在第二组测试用例中，温暖最多可以被分为 $2$ 份，蕴含的力量分别为 $2,3$ 。