题面描述

小杨正在和一个怪物战斗，怪物的血量为h，只有当怪物的血量恰好为0时小杨才能够成功击败怪物。 小杨有两种攻击怪物的方式：

1. 物理攻击：第i次使用物理攻击时，会对怪物造成 $2^{i-1}$ 点伤害。
2. 魔法攻击：选择任意一个不超过怪物当前血量的质数x，对怪物造成x点伤害；魔法攻击至多使用1次。 小杨想知道自己能否击败怪物，如果能，请求出最少需要多少次攻击。

   输入格式

   第一行包含一个正整数t，代表测试用例组数。 接下来t组测试用例，每组包含一个正整数h，代表怪物的血量。

   输出格式

   对于每组测试用例，如果可以击败怪物，输出最少攻击次数；否则输出-1。

   样例1

   输入样例

   3
   6
   188
   9999

   输出样例

   2
   4
   -1

   样例解释

   对于第一组测试用例，一种最优方案为：先使用魔法攻击选择质数5造成5点伤害，之后使用第1次物理攻击造成$2^{1-1}=1$点伤害，怪物血量恰好为0，总攻击次数为2。

   数据范围

   子任务编号	数据点占比	t	h
   1	20%	≤5	≤10
   2	20%	≤10	≤100
   3	60%	≤10	≤$10^5$

   全部数据满足 $1 \leq t \leq 10, 1 \leq h \leq 10^5$。