Finding the Largest Special Divisor

You are given a list of ( N ) integers. Your task is to find the largest positive integer ( P ) such that:

1. ( P ) divides the sum of the integers, i.e., ( P \mid \sum_{i=1}^{N} a_i ).
   
2. ( P ) is the greatest common divisor (GCD) of some non-empty subset of the list.
   
   In other words, you need to choose a non-empty subset of the given list whose GCD is ( P ), and in addition, ( P ) should be a divisor of the total sum of the list. It is guaranteed that at least one valid ( P ) exists for every test case.

inputFormat

The input is read from standard input (stdin).

The first line contains an integer ( T ) denoting the number of test cases. Each test case consists of two lines:

• The first line contains an integer ( N ) (the number of integers).
  
• The second line contains ( N ) space-separated integers ( a_1, a_2, \ldots, a_N ).

outputFormat

For each test case, output a single line containing the largest positive integer ( P ) that satisfies the given conditions. The output is written to standard output (stdout).## sample

2
4
4 8 12 16
6
18 24 30 42 48 54

4
6