가장 긴 등차 배열

등차 배열은 적어도 두 개의 정수를 포함하며 연속한 정수 사이의 차이가 모두 같은 배열이다. 예를 들어, $[9, 10]$, $[3, 3, 3]$, 그리고 $[9, 7, 5, 3]$은 등차 배열이지만, $[1, 3, 3, 7]$, $[2, 1, 2]$, 그리고 $[1, 2, 4]$은 등차 배열이 아니다.

Sarasvati에게 N개의 음이 아닌 정수로 이루어진 배열이 있다. 배열의 i번째 정수는 $A_{i}$이다. 그녀는 자신의 배열에서 길이가 최대인 연속 등차 부분 배열을 선택하려고 한다. 가장 긴 연속 등차 부분 배열의 길이를 구하도록 도와주자.

제한

시간 제한: 20초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. 0 ≤ $A_{i}$ ≤ $10^{9}$.

테스트 세트 1

2 ≤ N ≤ 2000.

테스트 세트 2

2 ≤ N ≤ 2 × $10^{5}$인 테스트 케이스는 최대 10개이다. 나머지 케이스에서는 2 ≤ N ≤ 2000.

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

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

예제 케이스 #1에서 다음의 대괄호 안에 있는 정수들은 가장 긴 연속 등차 부분 배열을 나타낸다: 10 7 $[4 6 8 10]$ 11

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

예제 케이스 #3에서 가장 긴 연속 등차 부분 배열은 $[5, 5, 5]$(네 번째 정수부터 여섯 번째 정수까지의 부분 배열) 또는 $[4, 5, 6]$(일곱 번째 정수부터 아홉 번째 정수까지의 부분 배열)이다.

예제 케이스 #4에서 가장 긴 연속 등차 부분 배열은 마지막 여섯 개의 정수이다.