Crazy old lady

Time limit2sMemory limit64 MB

Summary

From the recorded boarding seats under the displaced-passenger rule, recover the first boarder's assigned seat if it is unique and print 0 otherwise.

Level: Medium6 of 10
Topics: Simulation, Brute force
Solved: No attempts yet

Problem

This problem is a variation of a well known puzzle from probability theory. A plane has $N$ seats and there are $N$ passengers, so every seat is assigned. Passenger $i$ holds seat $i$ . Normally the passengers board one at a time in order of their seat number: the passenger who holds seat 1 boards first, then the passenger who holds seat 2, and so on.

Queues are too mainstream for the crazy old lady, so she goes ahead of everyone and boards first, even when her own seat is not seat 1. She then sits in whatever seat she likes, and by chance that may be her own seat.

After she has sat down, the remaining passengers board in order of their seat number and sit like this:

if the passenger's own seat is free, the passenger sits in it.
if the passenger's own seat is already taken, the passenger sits in any of the free seats.

Which seat does the last passenger get? Either the last passenger's own seat or the seat of the crazy old lady. Suppose the lady sits in seat $j$ , which is not her own. When the passenger who holds seat $j$ boards, that passenger has to pick some other seat out of the free ones, and the same thing happens again with later passengers. Once someone sits in the lady's own seat, every passenger after that gets their own seat.

You are given the seats in boarding order. Find the seat originally assigned to the crazy old lady.

Input

The first line contains the number of test cases $T$ ( $1 \le T \le 10$ ). Each of the next $T$ lines contains $N + 1$ numbers separated by spaces: first the number of seats $N$ ( $1 \le N \le 1000$ ), then $p_1, p_2, \ldots, p_N$ , where $p_i$ is the seat taken by the $i$ -th person to board. The input always describes a boarding that can really happen under the rules above.

Output

For each test case print one line. Print the seat assigned to the crazy old lady if the boarding determines it uniquely, and 0 otherwise.

Hint

On a plane with two seats where the first person to board sits in seat 2 and the second sits in seat 1, the answer is 0. The lady may be passenger 1, who sat in a seat that is not her own, or passenger 2, who sat in her own seat.

Examples1

Example 1
Input
```
2
2 2 1
4 2 3 1 4
```
Expected output
```
0
1
```