Minimize List Value

You are given multiple test cases. For each test case, you have an array of positive integers. You are allowed to perform the following operation any number of times: replace any element (x) with its integer square root (\lfloor \sqrt{x} \rfloor). The goal is to determine the minimum possible value that can appear in the array after applying a sequence of such operations.

Note: The integer square root of a number (x) is defined as (\lfloor \sqrt{x} \rfloor), i.e. the greatest integer less than or equal to (\sqrt{x}). It can be shown that for any positive integer, repeatedly applying the integer square root operation will eventually produce the number 1.

For example, if the input array is [10, 25, 16], you can repeatedly apply the operation until every number becomes 1, so the answer for that test case is 1.

inputFormat

The first line of input contains an integer (T) ((1 \le T \le 1000)) representing the number of test cases. Each test case is described in two subsequent lines. The first line contains an integer (M) (the number of elements in the array). The second line contains (M) space-separated positive integers.

outputFormat

For each test case, output a single line containing a single integer: the minimum possible value that can appear in the array after performing any number of the allowed operations.## sample

2
3
10 25 16
2
4 9

1
1