Александр купил себе новую колоду карт в киоске. Колода, которую он купил, содержит $$$n$$$ карт, на каждой из которых написано целое число от 0 до $$$10^9$$$.
Александр решил перемешивать колоду. Пусть $$$a_i$$$ — значение $$$i$$$-й карты с верха колоды. За одно перемешивание Александр выполняет следующие действия:
Если в колоде нет двух лежащих подряд карт с одинаковым значением, то при попытке ее перемешать методом Александра порядок карт в колоде не меняется.
Александр повторяет перемешивания, пока не встретит порядок карт, который уже встречался ранее. Александру стало интересно, сколько раз он перемешает колоду, прежде чем это произойдет. Помогите ему ответить на этот вопрос.
Вам необходимо решить задачу для одной или нескольких колод. В первой строке дано одно число $$$t$$$ — количество колод у Александра ($$$1 \le t \le 10^5$$$).
Далее следуют описания $$$t$$$ колод. Описание каждой колоды состоит из двух строк.
В первой строке дано одно число $$$n$$$ — количество карт в колоде ($$$1 \le n \le 2 \cdot 10^5$$$).
Во второй строке дано $$$n$$$ чисел $$$a_1, \ldots, a_n$$$ — исходный порядок карт, считая сверху ($$$0 \le a_i \le 10^9$$$).
Гарантируется, что сумма $$$n$$$ по всем колодам в одном тесте не превосходит $$$2 \cdot 10^5$$$.
Для каждой колоды выведите одно число — минимальное количество перемешиваний, после которого порядок карт в колоде совпадёт с одним из ранее встречавшихся.
3 5 0 1 1 2 2 5 0 1 2 1 0 4 1 2 2 1
2 1 2
Первая колода в примере для первого перемешивания будет разбита на кучки $$$[0, 1]$$$, $$$[1, 2]$$$, $$$[2]$$$. После объединения кучек в обратном порядке колода будет иметь вид $$$[2, 1, 2, 0, 1]$$$. Теперь в ней нет двух подряд идущих одинаковых карт и после второго перемешивания она не поменяется. Всего выполнено два перемешивания.
Во второй колоде сразу нет одинаковых подряд идущих карт, поэтому она не поменяется после первого же перемешивания.
Третья колода после первого перемешивания имеет вид $$$[2, 1, 1, 2]$$$, а после второго $$$[1, 2, 2, 1]$$$ и совпадает с изначальной.