#OJ2255. 骰子游戏

骰子游戏

骰子游戏

Time Limit: 1 Sec  Memory Limit: 128 MB

Description

单身狗范家铭决定通过一个小游戏来找一个聪明的学弟赠与甜蜜巧克力. 游戏规则如下: 1.玩家有一个骰子和一个计数器, 计数器初始值为0. 范家铭给玩家一个值, 玩家需要求出使得计数器的值恰好等于范家铭给的值的最小操作数. 2.骰子的初始状态为值为1的那一面朝上, 每次操作都可以使骰子转动90度, 使相邻的某一面朝上, 并且将操作后朝上的那一面的值累加入计时器中. 3.骰子初始的那个1不计入计数器中. 4.无法得到的数,输出-1

范真铭学弟非常想要得到范家铭学长的甜蜜巧克力, 所以请聪明的你来帮忙写一个程序来帮他计算答案.

Input

输入第一行是一个整数T(1 ≤ T ≤ 1000). 随后是T行输入, 每行一个数字n(1 ≤ n ≤ 10000), 代表计数器需要恰好等于的值.

Output

输出为T行, 每行一个数字, 代表最小步数.

Sample Input

2
5
10

Sample Output

1
2

HINT

n == 5, 操作步骤1->5, 步数为1步. n == 10, 操作步骤1->4->6, 步数为2步