题目描述

在日本的赛马当中，黄金船（gold ship）是著名的“追马”，而无声铃鹿（silence suzika）则是被冠以“异次元逃亡者”的“逃马”。今天，黄金船决定和铃鹿互换跑法，黄金船“逃跑”而铃鹿“追逐”。

这天，黄金船和铃鹿在一个 $4n-4$ 组成的方形环路上玩追逐游戏，方形的大小为 $n×n$ ，黄金船和无声铃鹿只能顺时针移动。一开始，黄金船位于右上角，无声铃鹿位于左下角。

游戏分为两轮进行：

1.调皮的黄金船在他目前的位置上设下陷阱。（铃鹿无法移动到带有陷阱的网格，但是黄金船无所谓）

2.黄金船可以移动 $2$~$3$ 格，铃鹿可以移动 $1$~$4$ 格。（黄金船先手，铃鹿移动结束后，一个回合结束）

游戏结束条件：

1. 在任意时刻，如果铃鹿在可以移动的 $1$~$4$ 格都有陷阱，则判定黄金船获胜
2. 而如果铃鹿和黄金船在同一个格子中，则判定铃鹿获胜

请问，铃鹿是否可以获胜？如果可以，请找到铃鹿获胜所需的最少回合数，此外，如果黄金船赢不了，他会尽量拖延最多的回合数从而让铃鹿最晚赢得比赛。

输入格式

第 $1$ 行输入 $t$ ($1~\\leq~t~\\leq~10^4$), $t$ 为测试组数

每组测试样例 第 $1$ 行输入 $n$ ($1~\\leq~n~\\leq~10^5$), $n$ 指该方形一行由为 $n$ 个小方形组成。

输出格式

对于每个测试样例，如果铃鹿注定要输掉比赛，则输出 $-1$ ，否则输出铃鹿在黄金船的拖延下获胜所需的最少回合数，每次询问占一行。

tips: cin,cout有可能超时，谨慎使用。

样例

2 
1 
2

0 
1

提示