题目描述

首领有 $h$ 点生命，只有生命恰好变为 $0$ 才算获胜。小泽第 $i$ 次物理攻击造成 $2^{i-1}$ 点伤害；他还可以至多进行一次魔法攻击，伤害可选为任意不超过当前生命的质数。求最少攻击次数，无解输出 $-1$。

输入格式

第一行整数 $t$，接下来 $t$ 行每行一个 $h$。

输出格式

每组输出最少攻击次数或 $-1$。

输入

1
54562

输出

3

输入

1
68532

输出

2

输入

1
39878

输出

2

数据范围

$1\le t\le10$，$1\le h\le10^5$。