Cho dãy gồm \(N\) phân số \(\frac{X_1}{Y_1}, \frac{X_2}{Y_2}, \dots, \frac{X_n}{Y_n}\).

Yêu cầu: Đếm xem có bao nhiêu phân số tối giản.

Input

Dữ liệu vào gồm \(N + 1\) dòng:

• Dòng đầu ghi số \(N\) (\(N < 10^3, N \in \mathbb{Z}^+\)).
• \(N\) dòng tiếp theo mỗi dòng ghi hai số \(X_i, Y_i\) cách nhau một dấu cách là tử số và mẫu số của phân số \(\frac{X_i}{Y_i}\) (\(1 \le X_i, Y_i \le 10^3, X_i, Y_i \in \mathbb{Z}^+\)).

Output

• Ghi ra một số nguyên duy nhất là số lượng các phân số tối giản.

Example

3
2 3
2 4
8 3

2