Description

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

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

• 物理攻击。假设当前为⼩杨第 $i$ 次使⽤物理攻击，则会对怪物造成 $2^{i-1}$点伤害。

• 魔法攻击。⼩杨选择任意⼀个质数 $x$（ $x$ 不能超过怪物当前⾎量），对怪物造成 $x$ 点伤害。由于⼩杨并不擅长魔法，他只能使⽤⾄多⼀次魔法攻击。

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

Input Format

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

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

Output Format

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

3
6
188
9999

2
4
-1

Hint

样例解释

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

数据范围

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

Source

GESP五级202409