Playing With Stones

Time Limit : 1 sec, Memory Limit : 262144 KB

石遊び

幸四郎くんと浮子さんは白と黒の石を使った遊びをしている。この遊びは以下のような内容である。

  1. 遊びの開始時に、いくつかの場を作り、それぞれの場に白石と黒石をそれぞれ1つ以上置く。
  2. 幸四郎くんと浮子さんは交互に、場をどれか選び、その場に対して以下の中から一つを選んで行動する。
    (ア) 白石を場から1つ取り除く。
    (イ) その場の白石の数を超えない個数だけ、黒石を1つ以上場から取り除く。
    (ウ) 黒石を1つ白石と交換する。このとき白石は石入れから持ってくる。石入れには十分な数の 白石が入っているものとする。
  3. 先に2ができなくなった人が負け。

幸四郎くんが先攻、浮子さんが後攻で何度かこの遊びをしているが、遊びの開始時に勝敗が決まるようである。そこで、幸四郎くんと浮子さんが最適な行動をとったときの、勝者を計算してみることにした。

遊びの開始時にそれぞれの場に置かれる白石と黒石の数が与えられたとき、幸四郎くんと浮子さんが最適な行動をとったときの勝者を求めるプログラムを作成せよ。

入力

入力は以下の形式で与えられる。

$N$
$w_1$ $b_1$
$w_2$ $b_2$
:
$w_N$ $b_N$

1行目に場の数$N$ ($1 \leq N \leq 10000$)が与えられる。続く$N$行には、それぞれの場の白石の数$w_i$と黒石の数$b_i$ ($1 \leq w_i, b_i \leq 100$)が与えられる。

出力

幸四郎くんが勝つ場合は「0」を、浮子さんが勝つ場合は「1」を、1行に出力する。

入出力例

入力例1

4
24 99
15 68
12 90
95 79

出力例1

0

入力例2

3
2 46
94 8
46 57

出力例2

1