Dữ liệu vào:

• Dòng đầu ghi số 𝑛 (𝑛~ ≤ 10^5, n ∈ 𝑍+~).
• 𝑛 dòng tiếp theo mỗi dòng ghi hai số 𝑥~_𝑖, 𝑦_𝑖~ ghi cách nhau một dấu cách là tử số và mẫu số của phân số (~1 ≤ 𝑥_𝑖, 𝑦_𝑖 ≤ 10^9, 𝑥_𝑖, 𝑦_𝑖 ∈ 𝑍+~).

Dữ liệu ra:

• Ghi số lượng các phân số tối giản.

Ví dụ:

Input

3
2 3
2 4
8 3

Output

2