J. Short Statement
time limit per test
2.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The setter of this problem hates long statements' problems, so the problem is:

The Score of array $$$b$$$ of size $$$m$$$ equals: $$$$$${\sum_{i = 1}^{m-1} gcd(b_i,b_{i+1})}$$$$$$

You are given an array $$$a$$$ of $$$n$$$ integers and an integer $$$k$$$.

You need to find a non-empty subsequence $$$a_{i_1}$$$, $$$a_{i_2}$$$, ..., $$$a_{i_m}$$$ with maximum Score such that:

$$$i_j \lt i_{j+1}$$$ and $$$i_{j+1}$$$ - $$$i_j$$$ $$$\le$$$ $$$k$$$ for all 1 $$$\le$$$ $$$j$$$ $$$\le$$$ $$$m - 1$$$.

Print the Score of this subsequence.

Input

The first line contains a single integer $$$t (1 \le t \le 100)$$$ — the number of testcases.

Then the descriptions of t testcases follow.

The first line of each testcase contains two integers $$$n$$$ and $$$k$$$— the size of the array $$$a$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) and $$$k$$$ explained above ($$$1 \le k \le n - 1$$$).

The second line consists of $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 4 \cdot 10^5$$$). It's guaranteed that the sum of $$$n$$$ over all testcases won't exceed $$$2 \cdot 10^5$$$.

Output

Output for each testcase the maximum Score.

Example
Input
2
5 1
2 4 8 16 32
5 2
2 4 1 16 32
Output
30
22