Сумасшедшая старушка

Следующая задача является вариацией известной головоломки из теории вероятностей. Есть n мест в самолете и все места проданы пассажирам. Пассажирам предлагается входить по одному, в порядке своих мест, от 1 до n (пассажир с номером места 1 входит первый, следующий входит пассажир с номером места 2, и так далее ...).

Как вы уже догадались, сумасшедшие старушки ненавидят очереди и предписания, поэтому они обычно идут впереди всех и входят первыми (несмотря на то, что у них может не быть первого места), кроме того, они занимают любое место, которое им нравится (случайно, может получится так, что они выберут свое собственное место).

После того как старушка заняла место, следующие пассажиры входят в порядке их мест (как описано выше) и рассаживаются следующим образом:

• если его/ее место пусто, то он/она занимает свое место.

• но если его/ее место уже занято, он/она занимает любое из оставшихся мест.Какое место достанется последнему пассажиру? Ответ прост: последний пассажир сядет либо на свое место либо на место сумасшедшей старушки!

Предположим, что сумасшедшая старуха занимает место j, которое не является ее собственным. Когда войдет пассажир, который был назначен на место j, он/она занимает какое то из свободных мест. Эта ситуация может повториться со следующими пассажирами. Но когда какой то пассажир сядет на место сумасшедшей старушки, очевидно (!) все следующие пассажиры сядут на свои собственные места. В этой задаче мы хотели бы узнать изначальное место сумасшедшей старушки.

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

Содержит несколько тестов. Первая строка содержит целое число t (1 ≤ t ≤ 10) тестов. Каждая из следующих t строк содержит n + 1 чисел, разделенных пробелом, сначала n (1 ≤ n ≤ 10^3), далее n чисел: места которые были заняты пассажирами в порядке их входа (p[1], p[2], ..., p[n] - где p[i] означает, что пассажир, который зашел i-ым занял место p[i]). Гарантируется, что входные данные правильные, то есть удовлетворяют условиям задачи.

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

Выведите место сумасшедшей старушки, если оно может быть определено однозначно, в противном случае, выведите 0.

Примеры

Примечание

В случае 2 2 1 мы не можем определить ответ однозначно, поскольку пассажир 1 является сумасшедшей старушкой, которая заняла чужое место, и пассажир 2 также может быть сумасшедшая старушка, которая села на свое место.