F. The Glass Bridge Challenge
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the Squid Game, players must cross a dangerous glass bridge consisting of $$$n$$$ planks. Each plank has a danger value $$$a_{i}$$$ , representing how unstable it is. Players must strategically place $$$k$$$ safe planks on the bridge to divide it into $$$k+1$$$ segments, making their path safer.

The survival cost of a segment is determined by the number of divisors ($$$\tau $$$) of the product of all danger values in that segment. The total survival cost is the sum of the survival costs of all segments.

For example, for a bridge $$$[20,1,1,1] $$$ and $$$k=1$$$, an optimal way is to divide the bridge into two segments: $$$[20]$$$ and $$$[1,1,1] $$$, and the total cost $$$=6+1=7$$$.

Your task is to strategically place the $$$k$$$ dividers to minimize the total survival cost, ensuring the safest possible route across the bridge. Can you survive the Glass Bridge Challenge and reach the other side?

Input

The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 500 $$$).

Each test case contains two lines :

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \leq n \leq 10^{3} , 1 \leq k \leq min(100,n-1) $$$), representing the number of the planks and the number of safe planks .

The second line contains $$$n$$$ integers $$$a_1,a_2, \ldots, a_n$$$ $$$(1 \leq a_i \leq 10^{6})$$$ representing the danger value of the planks.

Its guaranteed that the sum of $$$n$$$ over all test cases does not exceed 1000.

Output

Print one integer, the minimum total survival cost after optimally placing the safe planks.

It's guaranteed that the minimum total survival cost after optimally placing the safe planks does not exceed $$$10^{18}$$$.

Example
Input
5
5 1
20 1 1 1 1
5 2
4 6 8 2 3
4 1
2 3 4 5
3 1
4 6 8
5 2
2 12 9 24 8
Output
7
15
10
12
25
Note

In the second testcase, a best way is to divide the bridge into 3 segments $$$[4,6],[8,2],[3] $$$ so the total cost $$$=8+5+2=15$$$