가장 긴 등차 수열

Kick Start 2020 Round E에서(이 문제를 풀기 위해 이전 문제에 관해 알 필요는 없다) Sarasvati는 등차 배열에 대해 배웠다. 등차 배열은 적어도 두 개의 정수를 포함하고 연속한 정수 사이의 차이가 모두 같은 배열이다. 예를 들어, $[9, 10]$, $[3, 3, 3]$, $[9, 7, 5, 3]$은 등차 배열이지만, $[1, 3, 3, 7]$, $[2, 1, 2]$, $[1, 2, 4]$은 그렇지 않다.

Sarasvati에게 다시 $\mathbf{N}$개의 음이 아닌 정수로 이루어진 배열이 있다. 배열의 $i$번째 정수는 $\mathbf{A_i}$이다. 그녀는 배열에서 최대 하나의 원소를 자신이 원하는 임의의 정수(음수일 수도 있음)로 바꿀 수 있다.

배열 $\mathbf{A}$에 대해, Sarasvati는 부분 배열을 $\mathbf{A}$의 임의의 연속한 부분으로 정의한다. Sarasvati가 원래 배열에서 최대 하나의 원소를 바꾸어 만들 수 있는 가장 긴 등차 부분 배열의 길이를 구하도록 도와주자.

제한

시간 제한: 30초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$ $0 \le \mathbf{A_i} \le 10^{9}$.

테스트 세트 1

$2 \le \mathbf{N} \le 2000$.

테스트 세트 2

최대 $10$개의 테스트 케이스에 대해 $2 \le \mathbf{N} \le 3 \times 10^{5}$. 나머지 케이스에서는 $2 \le \mathbf{N} \le 2000$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 정수 $\mathbf{N}$를 포함하는 한 줄로 시작한다. 두 번째 줄에는 $\mathbf{N}$개의 정수가 주어진다. $i$번째 정수는 $\mathbf{A_i}$이다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호이며(1부터 시작), $y$는 가장 긴 등차 부분 배열의 길이이다.

예제 케이스 #1에서는 전체 배열이 등차 배열이므로, 가장 긴 등차 부분 배열은 전체 배열이다.

예제 케이스 #2에서 Sarasvati가 세 번째 위치의 수를 $5$로 바꾸면 배열은 $[5, 5, 5, 5, 5, 5, 4, 5, 6]$이 된다. 첫 번째 위치부터 여섯 번째 위치까지의 부분 배열이 가장 긴 등차 부분 배열이다.

예제 케이스 #3에서 Sarasvati는 마지막 위치의 수를 $-1$로 바꾸어 $[8, 5, 2, -1]$을 얻을 수 있다. 이렇게 얻은 배열은 등차 배열이다.