暂无测试数据。

两个人一起来到了桌游吧尝试一款叫做“扑克”的桌游。这副扑克一共有 $N$ 张牌分成两堆，其中 $1,3,5,...$ 在左边，$2,4,6,...$ 在右边。两个参与者开始时各选择一边，然后按照“正常扑克的规则”出牌。男左女右，散人理所当然的选择了右边，现在给出是谁先手，假设散人和优瓦夏都足够聪明，请你判断最后谁能获胜。

注:“正常扑克的规则”是指:

• 先由先手任意打出一张手牌
• 每当对手打出一张手牌后，己方有两种选择:
  1. 打出一张比这张牌点数大的牌
  2. 不打出任何牌。然后轮到对方任意打出一张手牌
• 先把手牌打完的一方获得游戏的胜利

输入格式

第一行一个正整数 $T$ ，表示数据组数。

接下来 $T$ 行，每行两个正整数 $n$，$op$。 $n$ 表示初始牌的总张数。 $op \in \lbrace 0,1 \rbrace$ 。$op=0$ 表示优瓦夏先出牌，$op=1$ 表示散人先出牌。

输出格式

$T$ 行每行输出 $0$ 或 $1$ 。$0$ 表示优瓦夏获胜，$1$ 表示散人获胜。

数据范围

对于 $40\%$ 的数据，$n \le 10$

对于 $70\%$ 的数据，$n \le 10000$

对于 $100\%$ 的数据，$2 \le n \le 10^{1000}$，$T \le 100$

2
5 0
10 1

0
1