Vì Lê và Bạc đã bàn xôn xao về chuyện mua gạch, bán đất rất dữ dội, nên sau khi biết tin Kiên - một đại gia chơi đất đã rất muốn thể hiện sự giàu có của mình bằng cách phát tặng ~N~ mảnh đất hình chữ nhật có chiều rộng là ~a_i~ và chiều dài là ~b_i~ cho mọi người . Do còn nhiều người muốn xin đất của Kiên nên bạn chỉ được phép chọn 1 mảnh đất trong ~N~ mảnh đất đó. Nhưng mà, đời không như là mơ, không ai cho không bạn thứ gì cả và Kiên cũng vậy, Kiên nói là muốn lấy đất của Kiên thì phải đạt một trong các điều kiện sau thì mới có thể lấy đất .

• Điều kiện ~1~: Chiều dài của mảnh đất phải chia hết cho chiều rộng ,thoả mản chiều dài mảnh đất là số siêu nguyên tố, khi đó bạn có thể nhận được mảnh đất đó, nhưng điều quan trọng là bạn cần tìm mảnh đất có diện tích lớn nhất và thoả mãn điều kiện trên .

• Điều kiện ~2~: Bạn chỉ được phép lấy mảnh đất có chiều dài và chiều rộng đều là số nguyên tố, khi đó bạn có thể nhận mảnh đất đó, nhưng Kiên lại không thích điều kiện này nên chỉ cho bạn mảnh đất thoả mãn điều kiện trên và có diện tích là nhỏ nhất .

• Điều kiện ~3~: Bạn không lấy đất thì bạn không có điều kiện và diện tích bạn nhận được là ~0~.

• Lưu ý: Theo cấp bậc nếu thoả mãn điều kiện ~1~ thì không được sử dụng các điều kiện còn lại, nếu không thoả mãn thì tăng loại điều kiện lên .

• Số siêu nguyên tố ở đây định nghĩa là số đó là nguyên tố là khi bỏ các số từ phải sang trái vẫn là số nguyên tố . Ví dụ số ~17~ ở đây không được gọi là số siêu nguyên tố vì ~17~ xoá ~7~ còn ~1~ không nguyên tố, nhưng ~23~ là số siêu nguyên tố vì ~23~ xoá ~3~ còn ~2~ vẫn nguyên tố.

Input

• Dòng 1 : Gồm số nguyên ~N~ ~(N \leq 10^5)~.
• Dòng 2 : Gồm ~N~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(a_i \leq 10^6)~
• Dòng 3 : Gồm ~N~ số nguyên dương ~b_1, b_2, ..., b_n~ ~(b_i \leq 10^6)~

Output

• Gồm một số nguyên là diện tích đất có thể lấy .

Sample Input 1

6
7 3 2 7 2 11
11 2 5 2 23 2

Sample Output 1

6

Sample Input 2

6
79 3 2 23 7 11
97 2 5 23 2 2

Sample Output 2

529

Note

• Ví dụ ~1~ : Chọn mảnh đất thứ ~2~ thoả mản điều kiện ~2~ có diện tích : ~2*3=6~ .
• Ví dụ ~2~ : Chọn mảnh đất thứ ~4~ thoả mản điều kiện ~1~ có diện tích : ~23*23=529~ .