蒜斜是杳瑶寺的住持，小美是吴遥寺的住持。作为当地最有名的两所寺庙，它们被合称为“杳瑶寺吴遥寺”。

一日，两寺决定合办一场别开生面的数学竞赛。蒜斜和小美选择与“杳瑶寺吴遥寺”读音接近的 114514，并且据此生成了一个无穷序列 $\{1,1,4,5,1,4,1,1,4,5,1,4,\cdots\}$。该数列由无穷个 $\{1,1,4,5,1,4\}$ 顺次拼接而成。

蒜斜不喜欢无穷序列，于是他希望选出该无穷序列的一个非空前缀 $A$。假设 $A$ 的长度为 $m$。

小美很喜欢数字 $n$ ，于是她希望把算式 $A_1 \otimes A_2 \otimes A_3 \cdots \otimes A_m$ 中的所有 $\otimes$ 替换成 $+,-$ 中的任意一个，使得算式计算结果恰好为 $n$。

由于可能会有很多的满足条件的 $m$，蒜斜想要知道其中最小的 $m$。

输入格式

本题有多组测试数据。

第一行一个正整数 $T$，表示数据组数。

对于每一组测试数据，第一行一个整数 $n$，表示小美喜欢的数字。

输出格式

对于每一组测试数据，一行一个正整数，表示满足条件的最小的 $m$。

样例一

input

9
-4
-3
-2
-1
0
1
2
3
4

output

3
7
3
4
2
1
2
4
3

限制与约定

对于所有测试数据，满足 $T = 10000$

Small Task: $|n| \le 10^6$。

Large Task: $|n| \le 10^9$。

时间限制：$3\texttt{s}$

空间限制：$512\texttt{MB}$

下载

样例数据下载