Bài toán:

Tế bào có một cá thể sinh vật ngoài hành tinh rất nhiều gen, mỗi gen trong chuỗi gen của tế bào đều có số lượng nào đó các nucleotide (ký hiệu là nu). Các chuyên gia thường quan tâm chuỗi gen của mỗi cá thể dưới dạng một chuỗi số lượng các nu (gọi là chuỗi nu), do đó chuỗi số này sẽ được gọi là độ dài của chuỗi. Mỗi gen được xem là đặc biệt nếu số nu của nó hoặc là bình phương của một số nguyên hoặc là lập phương của một số nguyên tố.

Đi nghiên cứu khả năng biến đổi gen của các loài sinh vật từ hệ gen, các nhà khoa học xem xét mẫu chuỗi nu của hai gen có thể phản ánh được mức độ giống nhau giữa chúng theo cách tìm ra chuỗi con chỉ gồm các gen đặc biệt mà có xuất hiện ở cả hai chuỗi nu (mỗi chuỗi con như vậy đều được gọi là chuỗi đặc trưng của hai chuỗi nu). Lưu ý rằng, chuỗi con của một chuỗi nu X, là chuỗi thu được từ X bằng cách giữ nguyên tất cả hoặc bỏ đi một số nào đó của các ký tự trong chuỗi X.

Yêu cầu:

• Xác định độ dài lớn nhất ~L~ của chuỗi đặc trưng chung của hai chuỗi nu cho trước.

Dữ liệu vào:

• Dòng đầu ghi lần lượt các số hàng của chuỗi nu thứ nhất.
• Dòng thứ hai ghi lần lượt các số hàng của chuỗi nu thứ hai.
• Tất cả các số hàng của chuỗi đều nguyên dương và không vượt quá ~10^{19}~.
• Độ dài của mỗi chuỗi nu đều không vượt quá 1000.

Kết quả:

• Một số nguyên ~L~ tìm được.

Ví dụ:

Input:

2 9 8 4 2 7 4 6
5 6 9 1 8 2 6 2 7 4 1

Output:

4