Hamako Online Judge

TLE
1sec

MLE
256MB

得点
12

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

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

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

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

入力

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

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

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

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