Description

有一天 $kk$ 拿到了一个长度为 $n(2\leq n\leq 10^6)$ 的序列，该序列为全排列( $1-n$ 之间的数字恰好仅出现一次，包括 $1$ 和 $n$)。现在 $kk$ 想知道这个序列中能构成的最大的 $gcd(a,b)(1\leq a < b \leq n)$

关于 $gcd$ ： 两个正整数 $a$ 和 $b$ 的最大公约数 $gcd(a,b)$ 是作为 $a$ 和 $b$ 的除数的最大整数。

Format

Input

第一行输入 $t(1\leq t\leq 1000)$，表示 $t$ 组数据。

接下来 $t$ 行，每行输入一个正整数 $n(2\leq n\leq 10^6)$，代表序列长度。

Output

输出 $t$ 行，对于每一行为该序列的最大 $gcd$ 值。

Samples

2
5
3

2
1

样例解释

在第一个样例中，$2$ 是可能的最大值，对应的是 $gcd(2,4)=2$。

在第二个样例中，$gcd(1,2)=gcd(2,3)=gcd(1,3)=1$。