Blackslex 正在为 Gean Dev 设计登录系统,发现大多数用户使用弱密码。
为了解决这个问题,他对所有密码提出了以下条件,依赖于两个变量 $$$k$$$ 和 $$$x$$$。每个密码都是一个长度为 $$$n$$$ 且满足这些属性的字符串 $$$s$$$。
- $$$s$$$ 仅使用英文字母表中前 $$$k$$$ 小写字母。
- 对于每对索引 $$$1 \le i \lt j \le n$$$ 使得 $$$(j-i)$$$ 可以被 $$$x$$$ 整除,字母 $$$s_i$$$ 和 $$$s_j$$$ 是不同的。
找到最小整数 $$$n$$$,使得不存在长度为 $$$n$$$ 的有效字符串。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 500$$$) — 测试用例的数量。
每个测试用例的第一行也是唯一一行包含两个整数 $$$k$$$ 和 $$$x$$$ ($$$1 \le k \le 26$$$, $$$1 \le x \le 15$$$)。
输出
对于每个测试用例,输出最小$$$n$$$。
示例
输入复制
32 13 21 5
输出复制
376
注意
对于第一个测试用例,没有长度为 $$$n=3$$$ 的有效字符串。对于 $$$n=2$$$,这样一个有效的例子是 ab。请注意,$$$(j-i)$$$ 唯一能被 $$$x=1$$$ 整除的对 $$$(i, j)$$$ 和 $$$1 \le i \lt j \le n$$$ 对于 $$$n=2$$$ 是 $$$(1, 2)$$$。
对于第二个测试用例,没有长度为 $$$n=7$$$ 的有效字符串。对于 $$$n=6$$$,这样一个有效的例子是 aabccb。请注意,$$$(j-i)$$$ 可被 $$$x=2$$$ 整除的所有对 $$$(i, j)$$$ 和 $$$1 \le i \lt j \le n$$$ 对于 $$$n=6$$$ 包括 $$$(1, 3)$$$, $$$(1, 5)$$$, $$$(2, 4)$$$, $$$(2, 6)$$$、$$$(3, 5)$$$ 和 $$$(4, 6)$$$。
对于第三个测试用例,没有长度为 $$$n=6$$$ 的有效字符串。对于 $$$n=5$$$,这样一个有效的例子是 啊啊啊。请注意,不存在 $$$(i, j)$$$ 可以被 $$$x=5$$$ 整除的对 $$$(i, j)$$$ 和 $$$n=5$$$ 的 $$$1 \le i \lt j \le n$$$。