n个格子排成一排，有m种颜色的蜡笔，Alice和Bob将在这些格子上进行涂色游戏，

规则如下： Alice先手，每个人每次必须选择一个Fibnacci数k并将连续k（1 ≤ k ≤ (n + 1）/ 2）个格子涂上一种颜色c，

已经涂过这种颜色的格子不能重复涂这种颜色，以红蓝两色为例，当Alice将格子涂成下图样式后

，Alice和Bob将不能再这些红色格子上重复的涂红色，即包含这些格子的涂色方案被视为非法，

但他们可以在1~4格子上涂上蓝色，涂完后样子可能会变成

即Bob将一个格子涂上蓝色，Alice将一个格子涂上蓝色。 

规定不能涂色者输掉这场游戏，现在问你谁赢得了这场游戏？

第一行输入一个正整数 t 代表进行t次游戏

接下来t行每行包括两个正整数n和m代表n个格子和m种颜色的蜡笔

数据范围：

1 ≤ t ≤ 1e6

1 ≤ n ≤ 1e18，1 ≤ m ≤ 1e18