该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

密码失效（Password）

题目描述

乐柠兔正在设计一个登录系统。为了避免用户使用过于简单的密码，他规定了两个参数 $k$ 和 $x$。

一个长度为 $n$ 的字符串 $s$ 被认为是合法密码，当且仅当它同时满足以下两个条件：

1. $s$ 只能使用英文字母表中的前 $k$ 个小写字母；
2. 对于任意两个下标 $i,j$，若 $1\le i<j\le n$ 且 $j-i$ 能被 $x$ 整除，则必须满足 $s_i\ne s_j$。

请你求出最小的正整数 $n$，使得不存在任何长度为 $n$ 的合法密码。

你需要独立处理 $T$ 组数据。

输入格式

第一行包含一个整数 $T$，表示测试数据组数。

接下来 $T$ 行，每行包含两个整数 $k$ 和 $x$。

输出格式

对于每组数据，输出一行一个整数，表示最小的无法构造合法密码的长度 $n$。

样例

样例输入 #1

3
2 1
3 2
1 5

样例输出 #1

3
7
6

样例解析

第一组数据中，$k=2,x=1$。任意两个不同位置的下标差都能被 $1$ 整除，因此任意两个字符都必须不同。只有 $2$ 种可用字母，所以长度为 $2$ 时仍可以构造，例如 ab；长度为 $3$ 时必然有两个位置字符相同，因此无法构造。

第二组数据中，$k=3,x=2$。下标奇偶性相同的位置之间必须使用不同字符。长度为 $6$ 时，奇数位和偶数位各有 $3$ 个位置，仍可以分别填入 $3$ 种不同字母；长度为 $7$ 时，奇数位有 $4$ 个位置，超过了可用字母数，所以无法构造。

第三组数据中，$k=1,x=5$。长度为 $5$ 时不存在两个下标差为 $5$ 的位置，所以可以全部填同一个字母；长度为 $6$ 时，第 $1$ 位和第 $6$ 位的下标差为 $5$，它们必须不同，但只有 $1$ 种字母，因此无法构造。

数据范围与约定

对于 $100\%$ 的数据，保证 $1\le T\le 500$，$1\le k\le 26$，$1\le x\le 15$。

• 特殊性质 A：保证 $x=1$。
• 特殊性质 B：保证 $k=1$。
• 特殊性质 C：保证 $k=26$ 或 $x=15$。