题目描述

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

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

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

输入格式

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

输出格式

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

输入输出样例

输入样例1

3
6
188
9999

输出样例1

2
4
-1

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

数据范围

对于全部数据，保证有 $1 \leq t \leq10$，$1 \leq h \leq10^{5}$。