410046: GYM103931 H Heirloom Painting

H. Heirloom Paintingtime limit per test2 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output Little Desprado2, the great artist, has a small painting robot to do some artistic creations.

Today, he draws a ring divided by $$$n$$$ grids, and there are $$$m$$$ kinds of colors. He wants to paint the ring as he wants. However, because of some technical issues – using a heirloom printer nozzle to save cost, for example – the robot will paint exactly $$$k$$$ continuous grids with the same color each time. In addition, the strong organic pigment can overlay the previous paintings, which means that the color applied later will replace the previous color.

Little Desprado2 wants to know the minimum number of times that his robot should paint from the empty grids to a given pattern, or it's impossible to do so.

Input

The first line contains one integer $$$T$$$ ($$$1\le T\le 10^5$$$), denoting the number of test cases.

For each test case, the first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1\le n, m\le 10^6, 1\le k\le n$$$), denoting the number of grids, colors and grids the robot will paint each time, respectively. The second line contains $$$n$$$ numbers $$$c_1,\ c_2,\ ...,\ c_n$$$ ($$$1\le c_i\le m$$$), $$$c_i$$$ denotes the color of the $$$i$$$-th grid that little Desprado2 wants.

There are no color at the beginning, and you can consider the uncolored grids with color $$$-1$$$ for simplicity.

It is guaranteed that sum of $$$n$$$ over all test cases won't exceed $$$10^6$$$.

Output

For each test case, print a single integer in a separated line - the minimal times the robot should paint. If the mission is impossible, print $$$-1$$$.

Example

Input

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

Output

6
5
-1

Note

For the first example, one optimal strategy is:

1. Paint grid $$$11$$$ and grid $$$1$$$ in color $$$1$$$. Note that this is a ring so grid $$$11$$$ and grid $$$1$$$ is adjacent.
2. Paint grid $$$2$$$ and grid $$$3$$$ in color $$$1$$$.
3. Paint grid $$$4$$$ and grid $$$5$$$ in color $$$2$$$.
4. Paint grid $$$6$$$ and grid $$$7$$$ in color $$$3$$$.
5. Paint grid $$$8$$$ and grid $$$9$$$ in color $$$3$$$.
6. Paint grid $$$9$$$ and grid $$$10$$$ in color $$$4$$$. Note that the color in $$$9$$$ is now replaced with $$$4$$$ from $$$3$$$.