小明最喜欢吃糖果了，于是买来了一包五彩缤纷水果糖，共n粒。当然，最好的东西要分享给最喜欢的人，于是他去找了小丽，要和小丽一起分掉这包水果糖。而小明想通过这包糖果为自己争取到一次和小丽共同去图书馆学习的机会，而小丽是计科班中的顶尖学霸，于是小丽制定了一套分糖果的规则:
1、小明和小丽轮流取糖果，小丽先取。
2、每个人每次取的糖果数量都有上限，最少为1粒，最多为m粒。
3、若小明可以取到最后一粒糖果，小明便可得到和小丽共同去图书馆学习的机会。

第一行输入为整数T(T<100)，表示T组测试数据
然后每行输入两个整数n和m，（1<=n<=1e5，1<=m<=n)

每组测试数据输出一个整数，1表示小丽取到最后一粒糖果，2表示小明取到最后一粒糖果