Jessica Pearson is going to celebrate her birthday. She remembers her childhood memories. So she decided to distribute chocolates among the employees of Pearson Specter firm. In Pearson Specter firm , there are N Departments. She decided to give equal no. of chocolates to each department head. But there should not be any conflict between employees of same department. It means all members of same department should get equal no. of chocolates.
As always, she wants the help of Harvey Specter to solve this problem. Harvey is extraordinary in handling law cases but very weak in Maths. Help Harvey to solve the problem.
Given the no. of employees in each department, find the minimum no. of chocalates she need to give to each department head.
INPUT:
The first line of the input contains a single integer T.
The first line of each test case contains a single integer N.
The Second line of each test case contains N space separated integers Ai where ith value denotes the no. of employees in ith department .
OUTPUT:
For each test case, print a single integer denoting minimum no. of chocolates required in a new line.
CONSTRAINTS:
1<=T<=100000
1<=N<=22
1<=Ai<=22
In sample test case 1, Jessica need at least 6 chocolates so that every employee of department 1 get 1 chocolate each.
In sample test case 2, Jessica need to give at least 6 chocolates to each department such that in first department each employee get 2 chocolates each and in second department each employee get 3 chocolates.
All the participants need to register on the given link: goo.gl/MDh9FR
