题目背景

藤原书记作为 TG 社的一员，十分热衷于开发小游戏，并让其他学生会成员一起来玩。

最近，她又发明了一种取纸牌的游戏，想让会长他们来尝试一下。不过，书记贯彻了她的作风，因此这款纸牌游戏存在某种必胜策略。

在被会长识破之后，她又来向你挑战。

题目描述

纸牌游戏 1 的规则如下：

初始有 $n$ 张纸牌，游戏双方轮流取纸牌，每次可以从剩余的纸牌里取出不超过 $m$ 张纸牌，不能不取，最后没有纸牌可取的一方就输了。

书记会向你发起 $T$ 次挑战，请你判断每一次游戏中，先手方和后手方，谁存在必胜策略。

输入格式

第一行一个整数 $T$，表示有 $T$ 次游戏。

接下来的 $T$ 行中，每行两个整数 $n,m$，表示在这次游戏中的初始纸牌数和单次取出纸牌数的最大值。

输出格式

输出共 $T$ 行，每行一个整数 $1$ 或 $-1$，表示这次游戏先手方或后手方存在必胜策略。

输入输出样例 #1

2
3 2
4 2

-1
1

说明/提示

【数据范围】 - 对于 $40\%$ 的数据，保证 $T\le 10$，$n,m\le 10^5$。

• 对于 $100\%$ 的数据，保证 $1\le T\le 10^6$，$1\le n\le 10^{18}$，$1\le m\le 10^9$。