背景

GESP五级真题(202409)

描述

⼩杨正在和⼀个怪物战⽃，怪物的⾎量为 $h$，只有当怪物的⾎量恰好为 0 时⼩杨才能够成功击败怪物。

⼩杨有两种攻击怪物的⽅式：

• 物理攻击。假设当前为⼩杨第 $i$ 次使⽤物理攻击，则会对怪物造成 $2^{i-1}$ 点伤害。
• 魔法攻击。⼩杨选择任意⼀个质数 $x$ （ $x$ 不能超过怪物当前⾎量），对怪物造成 $x$ 点伤害。由于⼩杨并不擅长魔法，他只能使⽤⾄多⼀次魔法攻击。

⼩杨想知道⾃⼰能否击败怪物，如果能，⼩杨想知道⾃⼰最少需要多少次攻击。

格式

输入

第⼀⾏包含⼀个正整数 $t$ ，代表测试⽤例组数。

接下来是 $t$ 组测试⽤例。对于每组测试⽤例，第⼀⾏包含⼀个正整数 $h$ ，代表怪物⾎量。

输出

对于每组测试⽤例，如果⼩杨能够击败怪物，输出⼀个整数，代表⼩杨需要的最少攻击次数，如果不能击败怪物，输出 -1。

样例

3
6
188
9999

2
4
-1

样例解释

对于第⼀组测试⽤例，⼀种可能的最优⽅案为，⼩杨先对怪物使⽤魔法攻击，选择质数 5 造成 5 点伤害，之后对怪物使⽤第 1 次物理攻击，造成 $2^{i-1}=1$ 点伤害，怪物⾎量恰好为 0 ，⼩杨成功击败怪物。

数据规模

对于全部数据，保证有$1 \le t \le 10, 1 \le h \le10^5$。

限制

时间限制：1.0 s

空间限制：512.0 MB