3988：[GESP202409五级] 挑战怪物

## 题目背景 2024 年 9 月 GESP C++ 五级编程第 2 题 ## 题目描述 ⼩杨正在和⼀个怪物战⽃，怪物的⾎量为 $h$ ，只有当怪物的⾎量**恰好**为 $0$ 时⼩杨才能够成功击败怪物。 ⼩杨有两种攻击怪物的⽅式： + 物理攻击。假设当前为⼩杨第 $i$ 次使⽤物理攻击，则会对怪物造成 $2^{i-1}$点伤害。 + 魔法攻击。⼩杨选择任意⼀个质数 $x$（ $x$ 不能超过怪物当前⾎量），对怪物造成 $x$ 点伤害。由于⼩杨并不擅长魔法，他只能使⽤⾄多⼀次魔法攻击。 ⼩杨想知道⾃⼰能否击败怪物，如果能，⼩杨想知道⾃⼰最少需要多少次攻击。 ## 输入格式 第⼀⾏包含⼀个正整数 $t$，代表测试⽤例组数。 接下来是 $t$ 组测试⽤例。对于每组测试⽤例，第⼀⾏包含⼀个正整数 $h$ ，代表怪物⾎量。 ## 输出格式 对于每组测试⽤例，如果⼩杨能够击败怪物，输出⼀个整数，代表⼩杨需要的最少攻击次数，如果不能击败怪物，输出 $-1$。 ## 样例1 ```input1 3 6 188 9999 ``` ```output1 2 4 -1 ``` ## 样例解释 对于第⼀组测试⽤例，⼀种可能的最优⽅案为，⼩杨先对怪物使⽤魔法攻击，选择质数 $5$ 造成 $5$ 点伤害，之后对怪物使⽤第 $1$ 次物理攻击，造成 $2^{1-1}=1$ 点伤害，怪物⾎量恰好为 $0$，⼩杨成功击败怪物。 ## 数据范围 | 子任务编号 | 数据点占比 | $t$ | $h$ | | ---------- | ---------- | --------- | ----------- | | 1 | $20\%$ | $\leq 5$ | $\leq 10$ | | 2 | $20 \%$ | $\leq 10$ | $\leq100$ | | 3 | $60\%$ | $\leq 10$ | $\leq 10^5$ | 对于全部数据，保证有 $1 \leq t \leq 10 ,1 \leq h \leq 10^5$。