問題文

あなたとGrantは、いわゆる「$21$言っちゃダメゲーム（棒取りゲームというところも）」をしている。

このゲームを何度やっても負けてばかりなので、ルールを拡張して正整数 $N$ と $K$ を使って以下のゲームを考える。

1. まず先攻のプレイヤーは $0$ が与えられる。
2. そこから $N$ 以上を宣言しないように（宣言したら負けになる）与えられた整数に $1$～$K$ のどれかの整数を加算したものを宣言し相手プレイヤーに渡す。
3. 勝負がつくまで代わり代わりに 2. を繰り返す。

このゲームは、$N$と$K$が決まったら、先手・後手、どちらが勝つかわかることが知られています。

このとき、$N,K$ を変えて、$1000$ 回ゲームを行うことにする。
まず最初のゲームはあなたが先攻としてゲームを開始します。
$2$ 回目以降のゲームでは、その前のゲームで負けたプレイヤーが自由に先攻か後攻かを選べます。
あなたもGrantもできるだけ勝つ回数が多くなるようにプレーするとしたとき、あなたが勝つ回数を求めてください。

あらかじめすべてのゲームの$N,K$は分かっているものとする。

入力

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

$N_i, K_i$ は $i$ 回目のゲームにおける $N,K$ の値です。
$N_i \geq 2$
$K_i \geq 2$
入力ファイルは4MBを超えない。

出力

あなたが勝つ回数を1行で出力してください。

サンプル

入力が $1000$ 行と大きいため、この問題にはサンプル入出力は用意されていません。
もしかしたら、No.8 N言っちゃダメゲームが参考になるかもしれません。