Codeforces Round 834 (Div. 3) |
---|
Закончено |
На доске написано положительное число $$$x$$$ длины $$$n$$$ в системе счисления с основанием $$$p$$$ ($$$2 \le p \le 10^9$$$). Число $$$x$$$ задано в виде последовательности $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i < p$$$) — цифры числа $$$x$$$ в порядке слева направо (от наиболее значащих к наименее).
Дмитрий очень любит все цифры данной системы счисления, поэтому он хочет увидеть каждую из них хотя бы один раз.
За одну операцию он может:
Например, $$$p=5$$$ и $$$x=234_5$$$.
Ваша задача — определить, за какое минимальное количество операций можно получить на доске все цифры от $$$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$$$.
Можно показать, что для этого всегда требуется конечное число операций.
112 31 24 21 1 1 16 61 2 3 4 5 05 21 0 1 0 13 101 2 35 10004 1 3 2 53 52 3 44 43 2 3 01 325 51 2 2 2 43 41 0 1
1 1 0 0 7 995 2 1 1 1 2
Название |
---|