Migrated from Lutece 1182 Hotaru's problem

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Hotaru Ichijou recently is addicated to math problems. Now she is playing with N-sequence. Let's define N-sequence, which is composed with three parts and satisfied with the following condition:

1. the first part is the same as the thrid part,
2. the first part and the second part are symmetrical. for example, the sequence 2,3,4,4,3,2,2,3,4 is a N-sequence, which the first part 2,3,4 is the same as the thrid part 2,3,4, the first part 2,3,4 and the second part 4,3,2 are symmetrical.

Give you n positive intergers, your task is to find the largest continuous sub-sequence, which is N-sequence.

Input

There are multiple test cases. The first line of input contains an integer T（T<=20）, indicating the number of test cases. For each test case: the first line of input contains a positive integer N（1<=N<=100000）, the length of a given sequence

the second line includes N positive integers ,each interger is no larger than 10^9 , descripting a sequence.

Output

Each case contains only one line. Each line should start with “Case #i: ”,with i implying the case number, followed by a integer, the largest length of N-sequence. We guarantee that the sum of all answers is less than 800000.

Samples

1
10
2 3 4 4 3 2 2 3 4 4

Case #1: 9

Resources

Prepare for 2015 MU2015 Multi-University Training