题目描述

布莱克斯设计登录系统时对密码提出了如下限制（由两个参数 $k$ 和 $x$ 决定）。密码为长度为 $n$ 的字符串 $s$，必须满足：

• 字符 $s$ 只使用英文字母表的前 $k$ 个小写字母；
• 对任意下标对 $1\le i<j\le n$，若 $(j-i)$ 能被 $x$ 整除，则要求 $s_i\ne s_j$。

问：对于给定的 $k$ 和 $x$，求使得不存在任何合法密码的最小正整数 $n$。

输入格式

第一行包含一个整数 $t$（$1\le t\le 500$），表示测试用例个数。

随后 $t$ 行，每行包含两个整数 $k, x$（$1\le k\le 26,\ 1\le x\le 15$）。

输出格式

对于每个测试用例，输出一行，包含一个整数——题目要求的最小 $n$。

样例输入

3
2 1
3 2
1 5

样例输出

3
7
6

说明

样例解释

对于第一个测试用例，没有长度为 $n=3$ 的有效字符串。对于 $n=2$ ，ab 就是这样一个有效示例。请注意， $(j-i)$ 能被 $x=1$ 整除的唯一对 $(i, j)$ 和 $n=2$ 的 $1 \le i < j \le n$ 是 $(1, 2)$ 。

对于第二个测试用例，没有长度为 $n=7$ 的有效字符串。对于 $n=6$ ，aabccb 就是这样一个有效示例。请注意， $(j-i)$ 可被 $x=2$ 整除的所有对 $(i, j)$ 和 $n=6$ 的 $1 \le i < j \le n$ 包括 $(1, 3)$ 、 $(1, 5)$ 、 $(2, 4)$ 、 $(2, 6)$ 、 $(3, 5)$ 和 $(4, 6)$ 。

对于第三个测试用例，没有长度为 $n=6$ 的有效字符串。对于 $n=5$ ，一个这样的有效示例是 aaaaa。