Sharmeen loves array very much. Many days ago she wrote an array (of n elements and the index of this array is 1 based) in her notebook, but unfortunately she lost the notebook. She want to restore the array. The only clue she know that is if in any position(i) of the array (1<= i < n), the element in this position is greater than, equal or less than the next position(i+1) element.

Can you help her to restore the array?

Input

In the first line given an integer t (1 <= t <= 100), which is the number of test cases.

For each test case,

In the first line there will be given a positive integer n (1 <= n <= 10⁵) which is the size of the lost array. In the next line there will be n - 1 integers X_i (0 <= X_i <= 2).

If, X_i = 0, then i^th  element is equal to (i+1)^th element of the lost array.

If, X_i = 1, then i^th  element is less than (i+1)^th element of the lost array.

If, X_i = 2, then i^th  element is greater than (i+1)^th element of the lost array.

Output

For each test case you have to output the lost array in one line. If multiple solution exist then you have to print the lexicographically smallest one. Elements of the lost array must be greater than zero.

For better understanding see the sample input output.

Example

Input:
1
5
1 2 0 1

Output:
1 2 1 1 2