Chef has a sequence A1,A2,,AN. Now for each index i (1iN) find the smallest index j such thatAj ocuurs exactly once in the subarray A[1,i]. If there is no such index J corresponding to a valid index i then print 1.

Input

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains a single integer N.

The second line contains N space-separated integers A1,A2,,,AN.

Output

For each test case, print a single line containing N space-separated integers the smallest index J for each i, or 1 if there is no such j corresponding to a valid index i.

Constraints

1T10

1N10^5

0Ai10^5 for each valid i.

Example Input

2 4 1 1 8 3 4 1 1 2 2

Example Output

1 -1 3 3 1 -1 3 -1