F. Всевозможные цифры
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На доске написано положительное число $$$x$$$ длины $$$n$$$ в системе счисления с основанием $$$p$$$ ($$$2 \le p \le 10^9$$$). Число $$$x$$$ задано в виде последовательности $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i < p$$$) — цифры числа $$$x$$$ в порядке слева направо (от наиболее значащих к наименее).

Дмитрий очень любит все цифры данной системы счисления, поэтому он хочет увидеть каждую из них хотя бы один раз.

За одну операцию он может:

  • взять любое число $$$x$$$, написанное на доске, увеличить его на $$$1$$$, и выписать на доску новое значение $$$x + 1$$$.

Например, $$$p=5$$$ и $$$x=234_5$$$.

  • Изначально на доске присутствуют цифры $$$2$$$, $$$3$$$ и $$$4$$$;
  • Дмитрий увеличивает число $$$234_5$$$ на $$$1$$$ и записывает число $$$240_5$$$. На доске присутствуют цифры $$$0, 2, 3, 4$$$;
  • Дмитрий увеличивает число $$$240_5$$$ на $$$1$$$ и записывает число $$$241_5$$$. Теперь на доске присутствуют все цифры от $$$0$$$ до $$$4$$$.

Ваша задача — определить, за какое минимальное количество операций можно получить на доске все цифры от $$$0$$$ до $$$p-1$$$ хотя бы по одному разу.

Входные данные

В первой строке входных данных дано единственное целое число $$$t$$$ ($$$1 \le t \le 2 \cdot 10^3$$$) — количество наборов входных данных. Далее следуют описания наборов входных данных.

Первая строка описания каждого набора входных данных содержит два целых числа $$$n$$$ ($$$1 \le n \le 100$$$) и $$$p$$$ ($$$2 \le p \le 10^9$$$) — длина числа и основание системы счисления.

Вторая строка описания каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i < p$$$) — цифры числа $$$x$$$ в системе счисления с основанием $$$p$$$

Гарантируется, что число $$$x$$$ не содержит ведущих нулей (то есть, $$$a_1>0$$$).

Выходные данные

Для каждого набора входных данных выведите одно целое число — минимальное количество операций, за которое Дмитрий сможет получить на доске все цифры от $$$0$$$ до $$$p-1$$$.

Можно показать, что для этого всегда требуется конечное число операций.

Пример
Входные данные
11
2 3
1 2
4 2
1 1 1 1
6 6
1 2 3 4 5 0
5 2
1 0 1 0 1
3 10
1 2 3
5 1000
4 1 3 2 5
3 5
2 3 4
4 4
3 2 3 0
1 3
2
5 5
1 2 2 2 4
3 4
1 0 1
Выходные данные
1
1
0
0
7
995
2
1
1
1
2