As you might already know, Ada the Ladybug is a farmer. She grows vegetables. At the moment, all her vegetables are in one furrow. She is going to replant them into a few new furrows (while keeping the order of the vegetables).

The total cost of growing the vegetables will be equal to the sum of absolute differences between neighboring vegetables. Ada wants to minimize the cost, can you help her?

Input

The first line of input contain 1 ≤ T ≤ 500 test-cases.

The first line of each test-case contains two integers N, K 1 ≤ N ≤ 2000, 1 ≤ K ≤ 20

The next line contains N integers 0 ≤ A_i < 10⁴, the costs of vegetables.

NOTE: The number of test-cases varies depending on size of array (the longest array won't be a single file more than once).

Output

For each test-cases, print the minimal costs.

Example Input

5
4 2
1 2 5 6
5 1
1 2 5 7 11
6 3
1 3 1 3 1 3
8 2
1 6 2 5 1 6 2 5
5 3
1 9 15 4 11

Example Output

2
10
0
6
5

Additional Information

TEST-CASE-1:
1 2
5 6
TEST-CASE-2:
1 2 5 7 11
TEST-CASE-3:
1 1 1
3 3 3

TEST-CASE-4:
1 2 1 2
6 5 6 5
TEST-CASE-5:
1 4
9 11
15

Example Input 2

1 
7 2 
2 5 7 4 8 8 4 

Example Output 2

5

Example Input 3

1
10 2
4 5 4 3 4 3 2 3 2 3

Example Output 3

4