Yêu cầu

Với 1 số nguyên n đã cho, hãy tìm số nguyên tố lớn nhất mà n chia hết.

Input

• Dòng đầu tiên gồm số nguyên dương T.

• T dòng tiếp theo, mỗi dòng gồm số nguyên dương n - 32 bit (n>1).

Giới hạn :T, n ≤ 10⁶

Output

T dòng, mỗi dòng là số nguyên tố lớn nhất mà n chia hết.