Background

Special for beginners, ^_^

Description

Alice 和 Bob 一起在玩一个游戏。

游戏一共有 $n$ 个存钱罐排成一排，其中第 $i$ 个存钱罐里面恰好装有 $i$ 元钱（ $i$ 从 1 开始）。游戏开始前，Alice 需要选择一个 $1到M$ 内的整数 $K$。接下来，游戏进行第 $j$ 轮时，Bob 会先拿走第 $j$ 个存钱罐内的钱，然后Alice 会拿走第 $((j\times K - 1) mod n)+1$ 个存钱罐内的钱（有可能他们每个人选择的存钱罐内的钱都已经被拿走了，那只能认倒霉）。

Alice 想知道：她要如何选择这个 $K$，使得自己拿走的钱最多？如果有多个 $K$ 符合要求，Alice 想知道最小的那一个 $K$ 是多少。

当确定 $K$以后，在游戏中，Alice 和 Bob都会在每轮游戏中拿走尽可能多的钱。

Format

Input

第一行输入一个正整数 $T(\le25)$，表示数据组数。

对于每一组数据，输入两个正整数 $n（\le10^9）, M（\le2000）$，分别表示存钱罐数量以及 Alice 能选择的 $K$ 的最大值。

Output

对于每一组数据，请输出能使得 Alice 拿的钱最多的最小的 $K$。

Samples

2
3 1
5 4

1
3

Limitation

1s, 1024KiB for each test case.