第四届华为杯程序设计竞赛D题目。问题输入

输入包括多个测试用例，首先给出测试用例数N，接着给出N个测试用例，每一个测试用例包括1行，首先给出正整数序列数M，接着依次给出M个正整数，1≤N≤100000，2≤M≤500000，正整数大小不超过1000。

问题输出

针对每一个测试用例，输出一行，给出对一系列正整数进行任意次变换后求得的最小之和。

样例输入

2

4 2 4 8 16

3 3 2 2

样例输出

8

3

-Problem input

Inputs include multiple test cases, test cases given first number N, then given N test cases, including a line for each test case, the first number given sequence of positive integers M, then turn gives M a positive integer, a ≤ N ≤ 100000,2 ≤ M ≤ 500000, positive integer size does not exceed 1000.

Problem Output

For each test case, output a line, given after a series of positive integers transform any number of times to obtain the minimum sum.

Sample Input

2

424816

3322

Sample Output

8

3