#2948. 挑战怪物【2024.9 GESP五级】

挑战怪物【2024.9 GESP五级】

挑战怪物【2024.9 GESP五级】

题目描述

⼩杨正在和⼀个怪物战⽃ ,怪物的⾎量为 h ,只有当怪物的⾎量恰好为 。时⼩杨才能够成功击败怪物。 ⼩杨有两种攻击怪物的⽅式: 物理攻击 。假设当前为⼩杨第 i 次使⽤物理攻击 ,则会对怪物造成 2i 1 点伤害。 魔法攻击 。⼩杨选择任意⼀个质数 ( 不能超过怪物当前⾎量) ,对怪物造成 点伤害 。 由于⼩杨并不擅长魔 法 ,他只能使⽤⾄多⼀次魔法攻击。 ⼩杨想知道⾃⼰能否击败怪物 ,如果能 ,⼩杨想知道⾃⼰最少需要多少次攻击。

输入格式

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

输出格式

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

输入输出样例 #1

输入 #1

3
6
188

输出 #1

2
4
-1

说明/提示

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

数据范围

子任务编号 数据点占比 t h 1 20% 5 ≤ 10 2 20% ≤ 10 ≤ 100 3 60% ≤ 10 ≤ 105 对于全部数据 ,保证有 1 ≤ t ≤ 1 , 1 ≤ h 105 。