Biến Đổi Cặp Số

Bessie likes cooking and wants to prepare a meal. She has a number of recipes and wants to pick one to use. However, she has a difficult time deciding between recipes, and she will cook the meal from the recipe that is chosen by a fair game.

This game involves a list of $n$ pairs of integers. Each pair of integers $(a_i,b_i)$ has some information written on it. In each step of the game, Bessie picks a pair and performs one of two operations on it:

• Operation A: $(a,b)\to (b,a+b)$
• Operation B: $(a,b)\to (a+b,b)$

The game continues until all pairs are of the form $(F_k,F_{k+1})$ for some integer $k\ge 1$, where $F_i$ is the $i$-th Fibonacci number.

How many pairs can Bessie modify?

Dữ liệu vào

Dòng đầu tiên chứa $n$ ($1\le n\le {10}^5$), số lượng cặp.

$n$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a_i$ và $b_i$ ($1\le a_i,b_i\le {10}^9$).

Dữ liệu ra

In ra số lượng cặp mà Bessie có thể biến đổi thành dạng $(F_k,F_{k+1})$.

Ràng buộc

$1\le n\le {10}^5$ $1\le a_i,b_i\le {10}^9$

Ví dụ