Problem Statement

You and Grant are playing the so-called "don't say $21$ game" (also known in some places as the stick-taking game).

Since you keep losing no matter how many times you play this game, you extend the rules and consider the following game using positive integers $N$ and $K$.

1. First, the player moving first is given $0$.
2. The player adds any integer from $1$ to $K$ to the given integer, declares the result, and passes it to the opponent, while trying not to declare a number that is $N$ or greater (a player who declares such a number loses).
3. The players alternately repeat step 2. until the game is decided.

It is known that once $N$ and $K$ are fixed, it can be determined which of the first player and the second player wins.

Now, you will play the game $1000$ times, with varying $N,K$.
You start the very first game as the first player.
In the $2$nd and later games, the player who lost the previous game may freely choose to be the first player or the second player.
Assuming that both you and Grant play so as to win as many games as possible, find the number of games you win.

The values of $N,K$ for all games are known in advance.

Input

$N_1$ $K_1$
$N_2$ $K_2$
$\vdots$
$N_{1000}$ $K_{1000}$

$N_i, K_i$ are the values of $N,K$ in the $i$-th game.
$N_i \geq 2$
$K_i \geq 2$
The input file does not exceed 4MB.

Output

Output the number of games you win on a single line.

Sample

Since the input is as large as $1000$ lines, no sample input/output is provided for this problem.
No.8 N言っちゃダメゲーム may be helpful.