Sunita has lots of tasks pending and she has no time to complete.  She needs your help and wants you complete the task.
You are given a list of integers and two values $N$ and $K$ $-$ the size of array of integers and the numbers of partitions to be made respectively.
You have to partition the list of integers without changing the order of elements ,into exactly $K$ parts. 
Calculate Greatest Common Divisor of all $K$ partition and sum up the gcd values for each partition.
Maximize the sum obtained. 
Can you help Sunita ? 

-----Input:-----
- First line will contain $T$, number of test cases. Then the test cases follow. 
- Each test case contains of a single line of input, two integers $N, K$. 
- Next line contains $N$ integers $-$ the list of integers.

-----Output:-----
For each test case, output in a single line integer $-$ the maximal result.

-----Constraints-----
- $1 \leq T \leq 100$
- $1 \leq N, K \leq 250$
- $1 \leq K \leq N$
- $1 \leq A[i] \leq 1e5$

-----Sample Input:-----
1
4 2
5 6 3 2

-----Sample Output:-----
6

-----EXPLANATION:-----
[5] [6 3 2] is the best partition [5 + GCD(6,3,2)] = 6

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "from sys import stdin,stdout\r\nfrom math import gcd\r\nfor _ in range(int(stdin.readline())):\r\n    # n=int(stdin.readline()) k-pieces\r\n    n,k=list(map(int,stdin.readline().split()))\r\n    a=list(map(int,stdin.readline().split()))\r\n    gr=[[0 for _ in range(n)]for _ in range(n)];ans=0;k-=1\r\n    for sz in range(n):\r\n        for i in range(n-sz):\r\n            j=i+sz\r\n            if sz==0:gr[i][j]=a[i]\r\n            else:\r\n                gr[i][j]=gcd(gr[i+1][j],gr[i][j-1])\r\n    # print(*gr,sep='\\n')\r\n    dp=[[0 for _ in range(n)]for _ in range(k+1)]\r\n    for i in range(n):\r\n        dp[0][i]=gr[0][i]\r\n    for i in range(1,k+1):\r\n        for j in range(i,n):\r\n            for par in range(j-1,-1,-1):\r\n                dp[i][j]=max(dp[i][j],gr[par+1][j]+dp[i-1][par])\r\n    # print(*dp,sep='\\n')\r\n    print(dp[k][n-1])\r\n\r\n"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13841