Spider sisters Grizella and Clementine will play a game called CatchEmAll. The game is played on N vertical pipes aligned one next to the other. The pipes are numbered 1 to N. Each second Grizella picks a single pipe and drops a ball down. Initially (at second 0) Clementine is standing below pipe number 1. Each second she may decide to stay under the same pipe or move 1 step to a neighboring pipe(left or right). It takes Clementine 1 second to make a single move. To make the game more interesting she is allowed to make at most K moves. Using her telepathic skills Clementine has read Grizella's mind and knows where Grizella will drop a ball each second. Help Clementine take advantage of this information. What is the maximum number of balls that Clementine can catch?

Note: when a ball is dropped it falls instantly, meaning Clementine can catch it only if she was standing right below the respective column at the exact time of drop.

Eg. At second 3 Clementine is standing below pipe 5. At second 4 Grizella drops a ball in pipe 4. Clementine can move from pipe 3 to 4 in 1 second and catch the ball.

Input

The first line of input contains one positive integer T (1 <= T <= 100), the number of test cases, followed by 2*T llines, each 2 lines describing a single case. For each case the first line contains three space separated integers N (2 <= N <= 10), K (1 <= K <= 1000) and S (1 <= S <= 1000). The second line contains S integers. Let’s denote each of them by t[i] (1 <= i <= S). t[i] (1 <= t[i] <= N) is the pipe number where Grizella will drop a ball at the i-th second.

Output

For each test case print in a new line the maximum number of balls Clementine can collect.

Constraints

Time limit: 3 seconds
Memory limit: 64 megabytes

Examples

input
3
5 1 2
3 4
3 2 3
1 3 1
3 5 8
2 2 2 2 2 2 2 3

output
0
2
8