When the new year comes, the patriarch will give red packets to everyone who comes to pay New Year's greetings. The patriarch has a pot of gold coins, which can be used to issue red packets. The grand patriarch needs to divide these gold coins into equal red packets, that is, the patriarch wants to give each person the same amount of gold coins. In order to let more people who come to visit the new year get red packets, the patriarch hopes to give as many people as possible red packets.
The patriarch asked you to help and issue red packets according to the above-mentioned rules, which would be difficult for you, so you asked the robot to help. Even the champion of go can be defeated by the robot, which is not a small business. Do you know how robot sends red packets?
In the first line, enter a positive integer T (1≤T≤29), indicating that there is T group of test data.
Each group of test data input has two lines, the first line is a positive integer N (0 < N < 66), which represents the number of gold coins; the next line is N positive integer sseparated by spaces (each positive integer < 66), respectively representing the amount of each gold coin.
The output of each group of test data takesup one line and is a positive integer, which represents the amount of gold in each red packet when it is divided into the most equal red packets.