Smallest Divisor Finder

Given an integer (n) with (n \ge 2), your task is to determine the smallest divisor of (n) that is greater than 1. In other words, if (n) is composite, find the smallest integer (d > 1) such that (d) divides (n). If (n) is prime, the smallest divisor is (n) itself. A common method to solve this problem efficiently is to check for divisibility by 2 and then test odd divisors up to (\sqrt{n}).

inputFormat

The first line contains an integer (T) (the number of test cases). Each of the next (T) lines contains a single integer (n) ((n \ge 2)). Input is provided via standard input (stdin).

outputFormat

For each test case, output the smallest divisor greater than 1 for the given integer (n) on a separate line. Output should be sent to standard output (stdout).## sample

4
10
17
21
49

2
17
3
7