伟大的艺术家 Little Desprado2 有一台小型绘画机器人来创作艺术品。
今天，他画了一个被分成 $n$ 个格子的环，并有 $m$ 种颜色。他想按照自己的意愿给这个环上色。然而，由于一些技术问题——例如为了节省成本使用传家宝打印喷嘴——机器人每次必须给恰好 $k$ 个连续的格子涂上相同的颜色。此外，强力有机颜料可以覆盖之前的画作，这意味着后涂上的颜色会覆盖之前的颜色。
Little Desprado2 想知道，从空白的格子开始，要达到给定的图案，机器人最少需要涂色多少次，如果无法完成任务，则输出 -1。
输入格式
第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。
对于每个测试用例，第一行包含三个整数 $n, m$ 和 $k$ ($1 \le n, m \le 10^6, 1 \le k \le n$)，分别表示格子的数量、颜色的种类以及机器人每次涂色的格子数。第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$ ($1 \le c_i \le m$)，$c_i$ 表示 Little Desprado2 想要的第 $i$ 个格子的颜色。
初始时没有任何颜色，为了方便起见，可以将未涂色的格子视为颜色 -1。
保证所有测试用例的 $n$ 之和不超过 $10^6$。
输出格式
对于每个测试用例，在单独的一行中输出一个整数，表示机器人最少需要涂色的次数。如果任务无法完成，则输出 -1。
样例
输入 1
3 11 4 2 1 1 1 2 2 3 3 3 4 4 1 5 2 1 1 2 1 2 1 6 2 2 1 2 1 2 1 2
输出 1
6 5 -1
说明
对于第一个样例，一种最优策略是：
- 用颜色 1 涂第 11 个格子和第 1 个格子。注意这是一个环，所以第 11 个格子和第 1 个格子是相邻的。
- 用颜色 1 涂第 2 个格子和第 3 个格子。
- 用颜色 2 涂第 4 个格子和第 5 个格子。
- 用颜色 3 涂第 6 个格子和第 7 个格子。
- 用颜色 3 涂第 8 个格子和第 9 个格子。
- 用颜色 4 涂第 9 个格子和第 10 个格子。注意，第 9 个格子的颜色现在被 4 覆盖了，不再是 3。