Stick Division

You have 'N' sticks of different lengths. You want sticks to be of equal length. You can cut any stick any number of times. Your task is to find the maximum length of the stick you can get.

Note:

The cuts in all the sticks will be of the same length.

For Example:

You have 4 sticks of sizes 4, 12, 20, 48. Now you want to cut sticks of equal length from each stick. Then you have the following options:

Make all the sticks of unit length.

Make all sticks of 2 unit length, 4(2*2), 12(2*6), 20(2*10), 48(2*24)

Make all the sticks of 4 unit length, 4(4*1), 12(4*3), 20(4*5), 48(4*12)

Hence, the maximum possible length of the stick is 4.

Input Format:

The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows. 

The first line of each test case contains an integer ‘N’ representing the number of sticks you have.

The next line contains 'N' space-separated integers, which denotes the size of the 'N' sticks.

Output Format:

For each test case, return the maximum possible length of the stick possible.

Note:

You don’t need to print anything or take input. This already has been taken care of.

Constraints:

1 <= T <= 100
2 <= N <= 5000
1 <= length[i] <= 10^6

Time Limit: 1 second