Trong một khu trưng bày cổ vật của LQDOJ, Prototype phát hiện ra một bộ sưu tập gồm nhiều vòng đá quý được sắp xếp theo thứ tự đặc biệt.

Mỗi chiếc vòng được tạo thành từ \(n\) viên đá, các viên đá được đánh số theo đúng thứ tự kết trên vòng.
Mỗi viên đá được mã hóa bởi một số nguyên từ \(1\) đến \(10^6\), đại diện cho màu sắc của nó.

Theo quy tắc đánh giá cổ xưa được khắc trên bệ trưng bày, độ thẩm mỹ của một chiếc vòng được định nghĩa là:

Số lượng lớn nhất các viên đá có thể chọn ra theo đúng thứ tự xuất hiện trên vòng (không nhất thiết phải liên tiếp nhau) sao cho dãy được chọn thỏa mãn đồng thời:

• Tất cả các viên đá trong dãy có mã màu có cùng số lượng ước số
• Hai viên đá kề nhau trong dãy được chọn phải khác mã màu

Ví dụ, với vòng đá có dãy màu:

• \(8\ 4\ 25\ 10\ 6\ 6\ 9\ 15\)

Một cách chọn tối ưu là:

• \(8,\ 10,\ 6,\ 15\)

Khi đó:

• Các số này đều có đúng \(4\) ước số
• Hai phần tử liên tiếp đều khác nhau

Vì vậy độ thẩm mỹ của vòng đá trên là 4.

Nhiệm vụ

Có \(r\) chiếc vòng đá khác nhau.

Hãy giúp Prototype xác định:

Độ thẩm mỹ lớn nhất trong số tất cả các vòng đá.

Input

• Dòng đầu chứa số nguyên \(r\) — số lượng vòng đá cần đánh giá (\(1 \le r \le 50\))
• Với mỗi vòng đá:
  • Dòng đầu chứa số nguyên \(n\) — số viên đá của vòng (\(1 \le n \le 1000\))
  • Dòng tiếp theo chứa \(n\) số nguyên \(a_i\) mô tả mã màu các viên đá theo thứ tự kết (\(1 \le a_i \le 10^6\))

Output

• In ra một số nguyên duy nhất là độ thẩm mỹ lớn nhất trong số \(r\) vòng đá

Example

3
8
8 4 25 10 6 6 9 15
5
13 18 1 12 20
7
21 8 5 26 12 9 35

4

Scoring

• Subtask 1 (\(30\%\) điểm): \(n \le 100\)
• Subtask 2 (\(40\%\) điểm): \(n \le 500\)
• Subtask 3 (\(30\%\) điểm): Không có ràng buộc thêm