On one fine day ma5termind's best friend Shasha told him that he is going to give him a gift. But Shasha does not like to spend too much money so he asked ma5termind to play a game called "Destroy the array" .
The game is as follows:
Given a list containing N integers. In one step, ma5termind will choose an integer from that list and add it to his score. After this step, shasha will remove all the multiples of chosen integer from the list. If list become empty after this step, game ends here otherwise ma5termind will continue the game with the list of remaining integers.
Shasha has already prepared his mind to give gift of value equilvalent to the score earned by the ma5termind. Therefore, ma5termind wants to score as much as possible.
Given list of N positive integers. Can you help ma5termind in finding out the maximum possible score he can get ?
Input:
Each input file will contain a T test case.
First line will contain a single integer N denoting number of elements in list.
Next line will contain a list of N integers Ai.
Ouput:
For each test case output the answer in new line.
Constraints:
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 100000
- 1 ≤ Ai ≤ 100000000
See sample I/O for more clarification.
Scoring:
- subtask 1: 1 ≤ T ≤ 10, 1 ≤ N ≤ 1000 ( 30 pts )
- subtask 2: 1 ≤ T ≤ 5, 1 ≤ N ≤ 105 ( 70 pts )
One of possible way of getting 17 is by first taking integers in the order (2,3,5,7) from the list.
