Smallest Prime Factor

Given an integer \(n\) greater than 1, your task is to compute its smallest prime factor. If \(n\) is a prime number, then its smallest prime factor is \(n\) itself.

You will be given \(t\) test cases. For each test case, you will be provided with a single integer and need to output the smallest prime factor of that integer.

The algorithm to determine the smallest prime factor is based on the observation that for any even number greater than 2, the smallest prime factor is 2. For an odd number, you only need to check odd factors up to \(\sqrt{n}\) to determine the smallest divisor.

inputFormat

The input is read from standard input (stdin) and consists of two lines. The first line contains a single integer \(t\) (the number of test cases). The second line contains \(t\) space-separated integers. Each integer \(n\) (\(n > 1\)) is a test case.

outputFormat

For each test case, output the smallest prime factor of the number. The results should be printed to standard output (stdout) as space-separated integers in a single line.

3
10 17 49

2 17 7