Alice and Bob like to travel. One day Alice went for a tour, and after coming back she described his tour to Bob. Bob got quite excited hearing the adventures Alice made. So, he planned to make a tour like Alice. As Alice told him that in Alice's path the two most interesting places were the first city and the last city she visited. So, Bob tries to make a tour that contains minimum number of cities and which starts from the city where Alice started her journey, and which finishes in the city where Alice finished her journey.

But the problem is that Bob doesn't have the map, so, he doesn't know the information of the roads between cities. But he has Alice's diary, so he figured out the cities Alice visited in order. It's known that there are bidirectional roads connecting the cities. And each city is identified by an integer between 1 and 50000.

Now Bob has given you the name of the cities visited by Alice in order, your task is to make a tour plan for Bob that visits least number of cities. Since there can be many such solutions, you have to find the tour which is lexicographically smallest. For example, let a tour be c₁, c₂ ... c_m and another tour be d₁, d₂ ... d_m, (c_i, d_i denote cities), then the first tour is lexicographically smaller if

• c₁ < d₁, or
• c₁ = d₁ and c₂ < d₂, or
• c₁ = d₁ and c₂ = d₂ and c₃ < d₃, or
• ...

Input starts with an integer T (≤ 20), denoting the number of test cases.

Each case starts with a line containing an integer n (2 ≤ n ≤ 50000). The next line contains n space separated integers denoting the tour made by Alice. Each of these integers will lie in the range [1, 50000]. Two adjacent integers: u v means that Alice moved to city v from city u. The starting city and the ending city will always be different. And two adjacent integers will also be different.

For each case, print the case number in a single line. The next line should contain the tour plan for Bob. Two integers in this line should be separated by a single space.

Dataset is huge, use faster I/O methods.