Gen đặc biệt chung

Người ta ghi lại hai dãy số nguyên dương mô tả hai mẫu gen. Một số được gọi là đặc biệt nếu nó là bình phương của một số nguyên dương nào đó, hoặc là lập phương của một số nguyên tố. (Ví dụ: \(1\), \(4\), \(64\) là số chính phương; \(8 = 2^3\) và \(27 = 3^3\) là lập phương của số nguyên tố.)

Hãy tìm dãy con chung dài nhất của hai dãy sao cho mọi phần tử của nó đều là số đặc biệt, và in ra độ dài của dãy đó (in \(0\) nếu không có dãy nào như vậy). Dãy con của một dãy nhận được bằng cách xoá một số phần tử và giữ nguyên thứ tự các phần tử còn lại.

Input

• Dòng thứ nhất chứa các phần tử của dãy thứ nhất.
• Dòng thứ hai chứa các phần tử của dãy thứ hai.

Số phần tử của mỗi dãy không được cho trước, các số cách nhau bởi dấu cách.

Output

In ra một số nguyên là độ dài dãy con chung đặc biệt dài nhất.

Constraints

• Mỗi dãy có từ \(1\) đến \(1000\) phần tử.
• Mỗi phần tử là số nguyên dương không vượt quá \(10^{18}\).

Sample Input

3 4 16 8 12 27 64 1 10
4 8 5 27 9 16 1 1 64

Sample Output

4

Explanation

Dãy thứ nhất giữ lại các số đặc biệt \(4, 16, 8, 27, 64, 1\); dãy thứ hai giữ lại \(4, 8, 27, 9, 16, 1, 1, 64\). Một dãy con chung dài nhất là \(4, 8, 27, 64\).