C. You and Assignments
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are a student enrolled in $$$n$$$ courses, and each course has a certain number of assignments, represented by an array $$$a$$$. The $$$i^{th}$$$ element of the array $$$a$$$ represents the number of assignments in the $$$i^{th}$$$ course. Your objective is to minimize the total number of assignments you need to complete across all courses. To reduce total number of assignments, you can apply the following operation any number of times (possibly zero) on the array,

  • Choose any element $$${a_i}$$$ of the array, let $$$i$$$ ($$$1 \leq i \leq n $$$) denotes its index in the array, and replace $$$a_i$$$ with $$$m^k\times({a_i} \mod m) + \left\lfloor \frac{a_i}{m} \right\rfloor$$$ where $$$m = 2 + i$$$ and $$$k$$$ is any integer such that $$$m^k \leq {a_i} \lt m^{k+1}$$$.
Find the minimum possible array sum after applying the above operations.
Input

Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t\leq 5\times 10^4$$$), the number of test cases. The description of the test cases follows.

The first line contains an integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$, the number of courses.

The second line contains $$$n$$$ space separated integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$), where $$$a_i$$$ represents the number of assignments in the $$$i$$$-th course.

The sum of $$$n$$$ over all test cases do not exceed $$$10^5$$$.

Output

For each test case output a single integer representing the minimum possible sum of the array.

Example
Input
4
1
1
2
4 2
3
6 10 2
4
1000000 4 10 5638383
Output
1
6
14
147578