D. Generatable Sequences
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You enter the prompt "Build me a generator for infinite energy. Make no mistakes." Unfortunately, your free trial of astra has ended, and you have been given a generator for infinite sequences instead.

Define $$$G_m$$$ as the set of all sequences that can be generated using the integer $$$m$$$. A sequence $$$c$$$ belongs to $$$G_m$$$ if at least one of the following conditions holds:

  1. The sequence $$$c=[1, 2, \ldots, m]$$$.

  2. There exist two (not necessarily distinct) sequences $$$a=[a_1,a_2,\dots,a_{|a|}]\in G_m$$$ and $$$b=[b_1,b_2,\dots,b_{|b|}]\in G_m$$$, and an integer $$$k$$$ with $$$0\le k\le |a|$$$, such that the sequence is obtained by inserting $$$b$$$ into $$$a$$$ after its first $$$k$$$ elements. In other words, the resulting sequence $$$c=[a_1,a_2,\dots,a_k,b_1,b_2,\dots,b_{|b|},a_{k+1},a_{k+2},\dots,a_{|a|}]$$$.

You are given an integer $$$m$$$ and a sequence $$$a_1,a_2,\dots,a_n$$$. Find the maximum length of a subarray$$$^{\text{∗}}$$$ of $$$a$$$ that appears as a subarray of some sequence in $$$G_m$$$.

Formally, find the maximum integer $$$k$$$ such that there exist a sequence $$$x\in G_m$$$ and indices $$$1 \le l_1 \le r_1 \le |a|, 1 \le l_2 \le r_2 \le |x|$$$ satisfying $$$r_1-l_1+1=r_2-l_2+1=k$$$ and $$$a_{l_1+i}=x_{l_2+i}$$$ for every $$$0\le i \lt k$$$.

$$$^{\text{∗}}$$$An array $$$a$$$ is a subarray of an array $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by the deletion of several (possibly zero or all) elements from the beginning and several (possibly zero or all) elements from the end.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$m$$$ and $$$n$$$ ($$$1\le m\le 10^9$$$, $$$1\le n\le 2\cdot 10^5$$$) — the generator and the length of the given sequence, respectively.

The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ ($$$1\le a_i\le m$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a single integer — the maximum length of a subarray of $$$a$$$ that occurs as a subarray of at least one sequence in $$$G_m$$$.

Example
Input
5
5 5
1 2 3 4 5
1000000000 5
1 5 1 5 1
3 8
1 2 1 2 3 3 1 3
1 1
1
10 5
4 5 6 7 8
Output
5
2
7
1
5
Note

For the first and fourth test cases, the entire sequence is generatable.

For the third test case, $$$\left[1, 2, 1, 2, 3, 3, 1\right]$$$ is a valid subarray.

For the fifth test case, $$$\left[4,5,6,7,8\right]$$$ is a subarray of $$$\left[1,2,3,4,5,6,7,8,9,10\right]$$$.