Một trung tâm kiểm định có ~n~ thiết bị được bố trí tại hai khu. Thiết bị thứ ~i~ có mã số nguyên dương ~a_i~ và thuộc khu ~g_i~, trong đó ~g_i~ bằng ~1~ hoặc ~2~.

Để kiểm tra khả năng phối hợp giữa hai khu, trung tâm ghép một thiết bị ở khu ~1~ với một thiết bị ở khu ~2~. Hai thiết bị được xem là tương thích nếu hai mã số không có ước chung nào lớn hơn ~1~.

Hãy đếm số cặp chỉ số ~(i,j)~, ~i < j~, sao cho hai thiết bị thuộc hai khu khác nhau và ước chung lớn nhất của ~a_i~ và ~a_j~ bằng ~1~.

Input

• Dòng đầu chứa số nguyên ~n~ ~(1 \le n \le 200000)~.

• Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa hai số nguyên ~a_i,g_i~ ~(1 \le a_i \le 10^6, g_i \in \{1, 2\})~.

Output

Số cặp chỉ số thỏa mãn.

Scoring

Sample Input 1

6
6 1
10 2
7 2
9 1
5 1
8 2

Sample Output 1

6

Notes

Sáu cặp chỉ số thỏa mãn là ~(1,3)~, ~(2,4)~, ~(3,4)~, ~(3,5)~, ~(4,6)~ và ~(5,6)~.