問題文

長さ $n$ の非負整数列 $A = (A_1, A_2, \ldots, A_n)$ と $n$ 以下の正整数 $k$ が与えられます。

あなたは、$A$ に対して以下の操作を $0$ 回以上の任意の回数行うことができます。

• $1\leq i _ 1\lt i _ 2\lt \cdots \lt i _ k \leq n$ なる整数 $i _ 1, i _ 2, \ldots, i _ k$ を選び、$A_{i _ 1}, A_{i _ 2}, \ldots, A_{i _ k}$ を $1$ ずつ減らす。

あなたの目標は、数列 $A$ が以下の条件を全て満たすようにすることです。

• $A _ 1, A _ 2, \ldots, A _ n$ は全て $k$ の倍数
• $A _ 1, A _ 2, \ldots, A _ n$ は全て $0$ 以上

目標が達成可能か判定し、達成可能な場合は目標を達成するまでの操作回数の 最小値 を求めてください。

1 つのファイルに対して $T$ 個のテストケースが与えられるので、その全てに対して上記の問題を解いてください。

入力

入力は以下の形式で標準入力から与えられます。

$T$
$\mathrm{testcase}_1$
$\mathrm{testcase}_2$
$\vdots$
$\mathrm{testcase}_T$

$\mathrm{testcase}_i$ は $i$ 番目のテストケースを表し、以下の形式で与えられます。

$n$ $k$
$A_1$ $A_2$ $\cdots$ $A_n$

• 入力は全て整数で与えられる
• $1\leq T\leq 2000$
• $1\leq k\leq n\leq 2000$
• $0\leq A_i\leq 10 ^ {15}$
• 全てのテストケースにわたる $n$ の合計は $2000$ 以下である

出力

$i$ 行目には $i$ 番目のテストケースに対する答えを出力してください。各テストケースに対する答えは、以下の形式で出力してください。

• 目標が達成不可能な場合は、-1 を $1$ 行に出力してください。
• 目標が達成可能な場合は、目標を達成するまでの操作回数の 最小値 を $1$ 行に出力してください。

$T$ 個目のテストケースに対する出力の後にも改行を入れてください。

サンプル

4
3 2
1 2 7
5 4
1 2 3 4 5
5 3
1 2 3 4 5
7 3
3 6 0 9 3 3 0

1
-1
2
0