ZYB is a smart guy. 

One day he learns a new method for representing trees: Euler tour technique (ETT). 

You can find more details about ETT on this web page: 

https://en.wikipedia.org/wiki/Euler_tour_technique.

https://blog.nowcoder.net/n/7afe88dc36ef4649b4de941f08abf576

If we use vertices rather than edges in ETT, then any tree with  vertices corresponds to a sequence of length , let's call it the vertex-ETT sequence.

In the beginning, ZYB generates a tree (the root of that tree is always 1) and writes down its vertex-ETT sequence. 
However, he spilt ink onto the paper by mistake and some numbers were covered in ink.
Can you help him to restore the sequence?

输入描述:

There are multiple test cases. The first line of the input contains an integer T, indicating the number of test cases. 
For each test case, the first line contains a integer N (), while the second line contains an integer sequence ( or , which means this number was covered by the ink) of length , the vertex-ETT sequence.

it is guaranteed that at least one valid sequence exists.
It's guaranteed that the sum of  of all test cases will not exceed . 
Due to the large size of the input, it's recommended to use a fast way to read the input.

输出描述:

For each case, print  space-separated integers, the recovered sequence.
If there are multiple solutions, print any of them.

2
3
1 2 1 -1 1
3
-1 2 3 -1 1

1 2 1 3 1
1 2 3 2 1