Bob có một dãy ~a~ gồm ~n~ số nguyên dương ~a_1, a_2, \dots, 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 \ne 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é.

Input

• 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 \le n \le 5 \cdot 10^5, 1 \le m \le 5 \cdot 10^5)~.

• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le 5 \cdot 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 ngay hôm đó, ngược lại cậu sẽ trả lại số nguyên này ngay hôm đó.

Output

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

Scoring

Sample Input 1

5 5
1 2 3 4 5
1
2
5
4
2

Sample Output 1

0
1
3
5
3

Sample Input 2

6 5
2 3 4 6 8 9
3
2
6
5
2

Sample Output 2

0
1
2
4
2

Notes

• 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)~.