Smallest Prime Factors

Given a list of positive integers, your task is to compute the smallest prime factor for each number. For any number n such that n > 1, its smallest prime factor is defined as the smallest prime number p that divides n (i.e. n \equiv 0 \pmod{p}). In case n = 1, since 1 has no prime factors, output -1.

Note: A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

Examples:

Input: 5
       30 45 13 100 27
Output: 2 3 13 2 3
Input: 5
2 3 5 7 11
Output: 2 3 5 7 11
Input: 1
1
Output: -1

</p>

inputFormat

The input is given in stdin in the following format:

• The first line contains a single integer n indicating the number of elements in the list.
• The second line contains n space-separated positive integers.

Constraints:

• 1 \le n \le 10⁵
• Each integer is positive and may be up to 10⁶

outputFormat

Print a single line containing n space-separated integers, where the i-th integer is the smallest prime factor of the i-th number in the input list. For numbers equal to 1, output -1.

## sample

5
30 45 13 100 27

2 3 13 2 3

</p>