题目描述

给定一个 $1$ 到 $n$ 的排列 $p$ 和一个正整数 $k$。

你可以对 $p$ 进行若干次操作，每次操作交换 $p_i$ 和 $p_j$，其中 $|i-j|=k$。你的目标是使得 $p$ 变为升序。

除此之外，在开始你的操作之前，你还可以预先交换任意两个 $p_i$ 和 $p_j$ 一次。

你的任务是判断：

1. 能否在不用预先交换的情况下，使得 $p$ 变为升序；
2. 如果不能，能否在预先交换一次的情况下，使得 $p$ 变为升序。

输入格式

本题有多组数据。第一行输入数据组数 $t$（$1\le t\le10^4$）。

对于每组数据，第一行输入 $n$ 和 $k$，第二行输入 $n$ 个整数，其中第 $i$ 个整数表示 $p_i$。

输出格式

对于每组数据：

• 如果满足条件 1 输出一行 0；
• 如果不满足条件 1 但满足条件 2 输出一行 1；
• 如果条件 1, 2 都不满足输出一行 -1。

说明/提示

$1\le t\le10^4$，$2\le n\le2\times10^5$，$1\le k\le n-1$，$1\le p_i\le n$。

每组数据的 $n$ 的总和 $\sum n\le2\times10^5$。

样例

6
4 1
3 1 2 4
4 2
3 4 1 2
4 2
3 1 4 2
10 3
4 5 9 1 8 6 10 2 3 7
10 3
4 6 9 1 8 5 10 2 3 7
10 3
4 6 9 1 8 5 10 3 2 7

0
0
1
0
1
-1