A. Blackslex и пароль
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Blackslex разрабатывает систему входа для Gean Dev и обнаружил, что большинство пользователей используют слабые пароли.

Чтобы решить эту проблему, он установил следующие условия, зависящие от двух переменных $$$k$$$ и $$$x$$$, для всех паролей. Каждый пароль представляет собой строку $$$s$$$ длиной $$$n$$$, удовлетворяющую этим свойствам.

  • $$$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. Обратите внимание, что единственная пара $$$(i, j)$$$, для которой $$$(j-i)$$$ делится на $$$x=1$$$ и $$$1 \le i \lt j \le n$$$ для $$$n=2$$$, это $$$(1, 2)$$$.

Для второго набора входных данных не существует допустимых строк длины $$$n=7$$$. Для $$$n=6$$$ одним из таких допустимых примеров является aabccb. Обратите внимание, что все пары $$$(i, j)$$$, для которых $$$(j-i)$$$ делится на $$$x=2$$$ и $$$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$$$ одним из таких допустимых примеров является aaaaa. Обратите внимание, что нет пар $$$(i, j)$$$, для которых $$$(j-i)$$$ делится на $$$x=5$$$ и $$$1 \le i \lt j \le n$$$ для $$$n=5$$$.