题目描述

本题中，我们用 $LCM(a, b)$ 表示 $a$ 和 $b$ 的最小公倍数，即最小的同时能够被 $a$ 和 $b$ 整除的正整数。

现在给你一个整数 $n$，你需要找到两个正整数 $a$ 和 $b$，满足：

$a + b = n$ 且 $LCM(a, b)$ 最小。

输入格式

输入包含多组测试数据，输入的第一行包含一个整数 $t(1 \le t \le 1000)$，表示测试数据组数。

接下来每组测试数据占一行，包含一个整数 $n(2 \le n \le 10^9)$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示满足 $a + b = n$ 的正整数 $a, b$ 对应的 $LCM(a, b)$ 的最小值。

input

3
4
6
9

output

2
3
6

说明/提示

样例解释

• 第1组测试数据：一种最优方案是选择 $a = b = 2$，此时 $LCM(2, 2) = 2$；
• 第2组测试数据：一种最优方案是选择 $a = b = 3$，此时 $LCM(3, 3) = 3$；
• 第3组测试数据：一种最优方案是选择 $a = 3; b = 6$，此时 $LCM(3, 6) = 6$。

数据规模与约定

• 对于 $10\%$ 的数据，$t = 1; n \le 100$
• 对于 $30\%$ 的数据，$t \le 10; n \le 10^5$
• 对于 $60\%$ 的数据，$t \le 100; n \le 10^7$
• 对于 $100\%$ 的数据，$1 \le t \le 1000; 2 \le n \le 10^9$