题目描述

在一些 贺云艾 玩的垃圾游戏中，有如下这种模型：

给你 $n$ 盏灯，每盏灯有两种状态：亮和灭。开始时所有灯都是灭的。每轮选择 $m$ 盏灯改变它们的状态，亮的灯会灭掉，灭的灯会亮起，当所有灯都亮起时，游戏成功。

贺云艾 想知道最少多少轮后可以使得所有灯都亮起，也就是说最欧的欧皇多少轮后可以通关？

输入格式

第一行一个整数 $T$ 表示有 $T(1\leq T \leq 20)$ 组数据。

之后 $T$ 行每行有空格分开的两个整数 $n,\ m(1\leq m\leq n\leq 5000)$ 如题意所示。

输出格式

每组数据输出一行表示最少多少轮使得所有灯亮起。

如果不存在方案使得所有灯亮起输出 $-1$。

样例

输入样例

2
5 3
4 2

输出样例

3
2