题目描述

$210$ 的因数有 $1,2,3,4,5,6,7,10,14,15,21,30,35, 42,70,105,210$。在这些因数中，质数有 $2,3,5,7$。

现在请你输入若干个数 ，输出每个数最大的质因数。

输入格式

第一行：输入一个整数 $T$，表示有 $T$ 组输入数据。

随后 $T$ 行：每行输入一个整数 $a_i$。

输出格式

对于每组输入数据，输出一个整数，表示这个数的最大质因数。

样例

3
10
17
600851475143

5
17
6857

数据范围

对于所有数据，$1≤T≤20，2≤a_i≤10^{12}$。