Alice likes visiting new places. Now he wants to visit a place called Strange Islands. There are N islands numbered from 0 to $N - 1$. From each island you can only go to one island. Alice can start on any island and visit others form that. Alice wants to visit as many islands as possible. Help him find the island, from which he starts, can visit maximum islands. If there are multiple such islands find the lowest numbered one.

Input
First line of the input is the number of test cases T. It is followed by T lines. Each test case contains N numbers. $i\;th$ number denotes the island number to which island i leads to.

Output
For each test case print a single number the required answer.

Constraints
$1 \le T \le 10$
$1 \le N \le 10^6$