Dũng là một nhà sưu tập vòng đá có thâm niên. Những chiếc vòng được kết từ nhiều viên đá, mỗi viên đá có một màu sắc khác nhau và thứ tự các viên đá tạo nên một độ thẩm mĩ nhất định.

Bên cạnh đó, Dũng cũng yêu thích số học nên đưa ra một định nghĩa hơi riêng biệt về độ thẩm mĩ. Dũng mã hóa màu sắc của các viên đá thành một số nguyên có giá trị từ ~1~ đến ~10^6~. Theo Dũng, độ thẩm mĩ của vòng đá là số lượng lớn nhất các viên đá xét theo thứ tự được kết (có thể không được kết liên tiếp nhau) tạo thành một dãy thỏa các điều kiện sau:

• Các viên đá trong dãy này có mã màu là các số nguyên có cùng số ước.
• ~2~ viên đá kề nhau trong dãy này phải khác màu nhau.

Chẳng hạn vòng đá có các màu ~8, 4, 25, 10, 6, 6, 9, 15~ có độ thẩm mĩ là ~4~.

Yêu cầu: Cho ~r~ các vòng đá khác nhau. Hãy giúp Dũng tìm vòng đá có độ thẩm mĩ cao nhất.

Input

• Dòng đầu tiên chứa số nguyên ~r~ (~1 \le r \le 50~) – số lượng các vòng đá cần thẩm định.
• Mỗi vòng đá được mô tả trên ~2~ dòng: dòng đầu chứa số nguyên ~n~ (~1 \le n \le 10^3~) là số lượng viên đá, dòng tiếp theo chứa ~n~ số nguyên là mã các viên đá được kết theo thứ tự tương ứng.

Output

Kết quả ghi ra một số nguyên là độ thẩm mĩ cao nhất của ~r~ vòng đá.

Sample Input 1

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

Sample Output 1

5