Nguyên tố cùng nhau

Cho hai dãy số nguyên dương \(A = a_1, a_2, \ldots, a_n\) và \(B = b_1, b_2, \ldots, b_m\).

Yêu cầu: Đếm số các chỉ số \(i\) của dãy \(A\) sao cho \(a_i\) nguyên tố cùng nhau (ước chung lớn nhất bằng \(1\)) với tất cả các số ở dãy \(B\).

Input

Dữ liệu vào gồm:

• Dòng thứ nhất chứa hai số nguyên dương \(n, m\) (\(n, m \le 10^6\));

• Dòng thứ hai chứa dãy số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(a_i \le 10^6\) với mọi \(i = 1 \ldots n\));

• Dòng thứ ba chứa dãy số nguyên dương \(b_1, b_2, \ldots, b_m\) (\(b_i \le 10^6\) với mọi \(i = 1 \ldots m\)).

Ràng buộc:

• Có \(30\%\) số điểm có: \(n, m \le 10^3\);

• Có \(30\%\) số điểm tiếp theo có: tất cả các số ở dãy \(A\) và dãy \(B\) đều là số nguyên tố;

• \(40\%\) số điểm còn lại không có ràng buộc gì thêm.

Output

In ra một số nguyên là số các chỉ số \(i\) tìm được.

Example

Input:

3 2
6 7 25
4 6

Output:

2

Note

Số \(6\) không nguyên tố cùng nhau với \(4\) (và \(6\)). Số \(7\) và số \(25\) nguyên tố cùng nhau với cả \(4\) và \(6\). Vậy có \(2\) chỉ số thỏa mãn.