题目背景

公平正义，需要牺牲。——《唐人街探案 3》

题目描述

现在有 $n$ 个人，lhm 有一个质量为 $1$ 的蛋糕。所有人都想吃到 lhm 的蛋糕。lhm 为了维持公平正义，他需要用最小的刀数将蛋糕分成相等的 $n$ 份（一份中可以包含多块）。

把蛋糕看作一个圆，注意：每次切蛋糕时只能沿着直径切下。

最终每人得到的蛋糕块数可以不同，但必须保证每人得到的质量为 $\frac1n$。

现在你需要求出 lhm 切割的最小刀数。

输入格式

本题包含多组数据。

输入数据共 $t+1$ 行。

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

接下来 $t$ 行，每行一个整数 $n$，表示人数。

输出格式

输出数据共 $t$ 行，每行一个正整数，表示答案。

2
2
3

1
2

提示

【样例解释】

当 $n=2$ 时，我们直接沿直径切下，从而得到了两个质量均为 $\frac 1 2$ 的蛋糕块，分别将它们分给两个人即可。

当 $n=3$ 时，我们可以先后沿两条夹角为 $60 \degree$ 的直径切下，从而得到了质量为 $\frac 1 6$ 的两个蛋糕块 $a,b$ 和质量为 $\frac 1 3$ 的两个蛋糕块 $c,d$。我们把 $a,b$ 分给第一个人，$c,d$ 分别给第二个人和第三个人，就可以做到公平正义。

【数据范围】

对于 $20\%$ 的数据满足，$1 \le n \le 10$。

对于另 $20\%$ 的数据满足，$t=1$。

对于 $100\%$ 的数据满足，$1 \le t \le 10^3$，$1 \le n \le 10^{9}$。