Bob có một dãy \(a\) gồm \(n\) số nguyên dương \(a_{1},\ a_{2},\ ...,\ a_{n}\).

Andy là bạn thân của Bob, cậu có một sở thích đặc biệt là mượn các con số của Bob về nhà  để chơi. Trong \(m\) ngày tới, mỗi ngày Andy sẽ tới mượn Bob một con số hoặc trả lại Bob một con số cậu đã mượn trước đó.

Tuy nhiên, có một điều kiện để Andy có thể mượn được các con số của Bob. Sau mỗi ngày, Bob đố Andy trong các con số cậu đang mượn, có bao nhiêu cặp số nguyên tố cùng nhau. Nói cách khác, Andy cần tính số cặp chỉ số \(i,\ j\ (i\
eq \ j)\) mà cậu đang mượn có \(gcd(a_{i},\ a_{j})\ = \ 1\).

Bạn hãy giúp Andy trả lời các câu đố này nhé.

Dữ liệu vào:

+ Dòng đầu tiên chứa hai số nguyên \(n,\ m\) là độ dài của dãy số của Bob và  số ngày
\((1 \leq n \leq 5 \times 10^{5},\ 1 \leq m \leq 5 \times 10^{5})\).

+ Dòng thứ hai chứa \(n\) số nguyên dương \(a_{1},\ a_{2},\ ...,\ a_{n}\ (1 \leq a_{i} \leq 5 \times 10^{5})\).

+ \(m\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(i\). Nếu trước đó Andy chưa mượn số nguyên \(a_{i}\), Andy sẽ mượn số nguyên này ngày hôm đó, ngược lại cậu sẽ trả lại số nguyên này ngày hôm đó.

Kết quả:

+ Gồm \(m\) dòng, dòng thứ \(i\) là đáp án cho câu đố trong ngày thứ \(i\).

Ví dụ:

Giải thích ví dụ:

+ Ngày đầu tiên Andy chỉ mượn Bob một số, vậy số cặp là  0.

+ Ngày thứ hai, các cặp nguyên tố cùng nhau là  (1, 2)

+ Ngày thứ ba, các cặp nguyên tố cùng nhau là  (1, 2), (2, 5), (1, 5).

+ Ngày thứ tư, các cặp nguyên tố cùng nhau là  (1, 2), (2, 5), (1, 5), (1, 4), (5, 4).

+ Ngày thứ năm, các cặp nguyên tố cùng nhau là  (1, 5), (1, 4), (5, 4).

Ràng buộc:

+ Subtask 1 (20% điểm): \(n,\ m\ \leq \ 100\).

+ Subtask 2 (30% điểm): \(n,\ m\ \leq \ 103\).

+ Subtask 3 (50% điểm): không có ràng buộc gì thêm.