#216827. [GKS 2021 #B] Longest Progression

In Kick Start Round (you do not need to know anything about the previous problem to solve this one) Sarasvati learned about arithmetic arrays. An arithmetic array is an array that contains at least integers and the differences between consecutive integers are equal. For example, , , and are arithmetic arrays, while , , and are not.

Sarasvati again has an array of non-negative integers. The -th integer of the array is . She can replace at most element in the array with any (possibly negative) integer she wants.

For an array , Sarasvati defines a subarray as any contiguous part of . Please help Sarasvati determine the length of the longest possible arithmetic subarray she can create by replacing at most element in the original array.

The first line of the input gives the number of test cases, . test cases follow. Each test case begins with a line containing the integer . The second line contains integers. The -th integer is .

For each test case, output one line containing Case #x: followed by , where is the test case number (starting from ) and is the length of the longest arithmetic subarray.

样例输入 1

3
4
9 7 5 3
9
5 5 4 5 5 5 4 5 6
4
8 5 2 0

样例输出 1

Case #1: 4
Case #2: 6
Case #3: 4

In Sample Case #, the whole array is an arithmetic array, thus the longest arithmetic subarray is the whole array.

In Sample Case #, if Sarasvati changes the number at third position to , the array will become . The subarray from first position to sixth position is the longest arithmetic subarray.

In Sample Case #, Sarasvati can change the number at the last position to , to get . This resulting array is arithmetic.

Limits

.

.

Test Set

.

Test Set

for at most test cases.

For the remaining cases, .