Macau casino has a popular game: horse racing. However, the rule is different from the normal ones. It is about  guessing the kth fastest horse. Joy wants to apply a job in the casino, but his boss give him a test. He can get the job only if he passes the test. The rules are as followed:

Given the strength of n horses, (to simplify, the strength of the n horses is a permutation of 1 to n, and horse with larger strength run faster), the boss wants to know the sum of all the kth fastest horse in every consecutive interval of the n horses, and remember only the intervals equal or longer than k should be considered.

Joy is not good at math, so he turns to you for help.

There is only one integer T (1 <= T <= 10) in the first line, denoting the number of test cases.

For each test case, the first line includes two integers n and k. k <= min(n, 80), the sum of n in all test cases does not exceed 5 * 10⁵. The second line is the strength of the n horses.

For each test case, output a line containing the answer.