← 返回题目列表

Codeforces · 2179/A

A. Blackslex 和密码

中文机器翻译题面 查看原题

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$$$。

示例

输入
复制

3
2 1
3 2
1 5

输出
复制

3
7
6

注意

对于第一个测试用例,没有长度为 $$$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$$$。