Rohit was travelling to NIT Warangal, to attend their annual technical fest - "Technozion". In the train, opposite to him, Rohit found quite a peculiar man playing with an array of numbers. When he enquired, the man told that he is trying to solve a puzzle for decades but unable to do so. Seeing Rohit's interest in the puzzle, the man decided to challenge him to solve it, in return of which he would pay Rohits return fare. Rohit got excited and decided to solve it but requires your help. Help him solve the puzzle which is as follows -

You are given an array of size N ( 1-based indexing ) , filled with positive integers not necessarily distinct.
You are now asked to play a game on it.
For the first step any number (except the first number) can be chosen.
At each step of the game, you have to select a number whose index is the multiple of any one of the indices of previously selected numbers.
You have to maximise the sum of all the numbers that you can choose using the rule mentioned.
You can leave the game with current sum at any time or continue to play till it is possible to choose a number.
Ofcourse, you have to choose optimised indices to get the maximum sum.
You cant choose an index twice

Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the size of the array . The second line contains N space-separated integers A1, A2, ..., AN denoting the elements of the array.

Output
For each test case, output a single line containing the maximum sum possible following the rules of the game.

Constraints

1 ≤ T ≤ 10
2 ≤ N ≤ 10^5
0 ≤ Ai≤ 10^9

Example
Input:
1
8
1 2 3 4 5 6 7 8

Output:
20

Explanation
Rohit found out that the maximum sum possible in the given test case is 20.

见题面

见题面