Ohani has recently learned about complete binary tree and binary search tree. Now she wants to create a complete binary tree and insert some value in the nodes such that it maintains the property of a binary search tree. She calls this tree Complete Binary Search Tree. So she takes a sorted array and one by one she inserts the values in a complete binary tree to create Complete Binary Search Tree (CBST).

A binary tree is called a Binary Search Tree if for each node u, the value of u is greater than every value in the left subtree of u and is less than every value in right subtree of u.

A binary tree is said to be complete if all its levels, expect possibly the last, have the maximum number of possible nodes, and if all the nodes at the last level appears as far left as possible. So, there is a unique complete tree for n nodes. Here is a complete tree of 10 nodes.

Let a sorted array of five element is: 1 3 4 6 9. So, the CBST of this array is:

But suddenly she comes through a problem. Her teacher gave her an array which is unsorted. So, she first sort the array and then use the sorted array to create CBST. To sort the array, she takes any elements and place it at any place in the array in one step. For example: if an array is: 1 4 2 3, she can take 2 and place it after 1, she can then take 4 and place it after 3, so, total 2 steps sorts the array. But this is not the minimum. Now your task is to find the minimum number of steps needed to sort an unsorted array using Ohani's procedure and then build a CBST.

Input

The first line of the input contains an integer T (1<=5) denoting the number of test cases.

Each test case contains of two lines. First line contains an integer N (1 <= N <= 100000),  the number of elements in the array.
Next line contains N distinct numbers where each numbers will be between 1 to N.

Output

For each test case, you need to output the case number on  the first line.
In the second line you have to output the minimum numbers of steps required to sort the array.
In the third line, for each  value from 1 to N, the parent of these values in the built CBST. The parent of the root is -1.

For example, for if the given array is: 1 4 2 3, then the output for the CBST is,

2 3 -1 3

Because, the parent of value 1 is 2, the parent of value 2 is 3, 3 is the root, so, its parent is -1, the parent of 4 is 3.

Example

Input:
1
4
1 4 2 3

Output:
Case 1:
Minimum Move: 1
2 3 -1 3