题目描述

Petya 收到了一款单人卡牌游戏“礼炮”。牌堆中有 $n$ 张牌，每张牌上写着 $1$ 到 $m$ 的一个整数。

游戏开始时，牌堆被打乱，玩家拿起牌堆顶部的 $k$ 张牌。任意时刻手牌数量不能超过 $k$。玩家可以进行三种操作：

1. 丢弃手中的任意一张牌，该牌不能再使用；
2. 若牌堆中还有牌，且手牌数严格小于 $k$，可以摸牌堆顶部一张牌；
3. 从手中打出一张牌。若该牌数字为 $x$，只有当玩家已经打出了 $1,2,\ldots,x-1$，且还没有打出 $x$ 时，才能打出它。

游戏在无法进行任何操作时结束。目标是尽可能多地打出牌。

Petya 偷看到了牌堆顺序，请你求他最多能打出多少张牌。

输入格式

输入包含多个测试。第一行一个整数 $T$，表示测试组数。

每组测试两行：

第一行三个整数 $n,m,k$。

第二行 $n$ 个整数 $a_i$，表示牌堆从上到下的顺序。

保证所有测试中 $n$ 的总和不超过 $10^5$。

输出格式

对每组测试，输出一行一个整数，表示最多能打出的牌数。

样例

样例输入

3
4 3 1
3 2 1 2
1 2 1
2
5 5 2
4 2 1 4 3

样例输出

2
0
4

样例说明

第三组中，初始手牌为 4 和 2。先丢弃 4，摸到 1，随后打出 1 和 2。然后摸到 4，再摸到 3，最后打出 3 和 4。