Problem: <image>

William is a huge fan of planning ahead. That is why he starts his morning routine by creating a nested list of upcoming errands.

A valid nested list is any list which can be created from a list with one item "1" by applying some operations. Each operation inserts a new item into the list, on a new line, just after one of existing items a_1  .  a_2  .  a_3  .   ⋅⋅⋅   .\,a_k and can be one of two types: 

  1. Add an item a_1  .  a_2  .  a_3  .  ⋅⋅⋅  .  a_k  .  1 (starting a list of a deeper level), or 
  2. Add an item a_1  .  a_2  .  a_3  .  ⋅⋅⋅  .  (a_k + 1) (continuing the current level). 

Operation can only be applied if the list does not contain two identical items afterwards. And also, if we consider every item as a sequence of numbers, then the sequence of items should always remain increasing in lexicographical order. Examples of valid and invalid lists that are shown in the picture can found in the "Notes" section.

When William decided to save a Word document with the list of his errands he accidentally hit a completely different keyboard shortcut from the "Ctrl-S" he wanted to hit. It's not known exactly what shortcut he pressed but after triggering it all items in the list were replaced by a single number: the last number originally written in the item number.

William wants you to help him restore a fitting original nested list.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 10). Description of the test cases follows.

The first line of each test case contains a single integer n (1 ≤ n ≤ 10^3), which is the number of lines in the list.

Each of the next n lines contains a single integer a_i (1 ≤ a_i ≤ n), which is what remains of William's nested list.

It is guaranteed that in each test case at least one fitting list exists.

It is guaranteed that the sum of values n across all test cases does not exceed 10^3.

Output

For each test case output n lines which represent a valid nested list, which could become the data provided to you by William.

If there are multiple answers, print any.

Example

Input


2
4
1
1
2
3
9
1
1
1
2
2
1
2
1
2


Output


1
1.1
1.2
1.3
1
1.1
1.1.1
1.1.2
1.2
1.2.1
2
2.1
2.2

Note

In the second example test case one example of a fitting list is:

1

1.1

1.1.1

1.1.2

1.2

1.2.1

2

2.1

2.2

This list can be produced by using the sequence of operations shown below: <image>

  1. Original list with a single item 1. 
  2. Insert item 2 by using the insertion operation of the second type after item 1. 
  3. Insert item 1.1 by using the insertion operation of the first type after item 1. 
  4. Insert item 1.2 by using the insertion operation of the second type after item 1.1. 
  5. Insert item 1.1.1 by using the insertion operation of the first type after item 1.1. 
  6. Insert item 1.1.2 by using the insertion operation of the second type after item 1.1.1. 
  7. Insert item 1.2.1 by using the insertion operation of the first type after item 1.2. 
  8. Insert item 2.1 by using the insertion operation of the first type after item 2. 
  9. Insert item 2.2 by using the insertion operation of the second type after item 2.1. 

Solution (in CPP):

Solution:
                    /**************************************************************************************
                    *                                        Poet :                                       *
                    |                                       Arnab048                                      |
                    *                                   (codingjedi048)                                   *
                    |                               codingjedi048@gmail.com                               |
                    **************************************************************************************//*
                                            I have a clumsy apprentice called Einstein.                                          
*/#include<bits/stdc++.h>
using namespace std;
//constants : 
const int   N                               = (int) 1e6+5;
const int   M                               = (int) 1e9+5;
const int   mod                             = (int) 1000000007;
const int   max_prime                       = (int) 1e6+3;
//data_type_compressions :
#define     ll                              long long int
#define     ull                             unsigned long long int 
#define     ui                              unsigned int 
//STL : 
#define     vi                              vector<int>
#define     vb                              vector<bool>
#define     vs                              vector<string>
#define     vl                              vector<ll>
#define     si                              set<int>
#define     sl                              set<ll>
#define     ip                              pair<int,int>
#define     lp                              pair<ll,ll>
#define     ips                             pair<string,int>
#define     lps                             pair<string,ll>
#define     ipc                             pair<char,int>
#define     lpc                             pair<char,ll>
#define     vip                             vector<ip>
#define     PQ                              priority_queue
#define     vlp                             vector<lp>
#define     hashmap                         unordered_map
#define     msi                             multiset<int>
#define     msl                             multiset<ll>
#define     pb                              push_back
#define     spb                             insert
#define     all(x)                          x.begin(),x.end()
#define     all_0(x)                        memset(x,0,sizeof(x))
#define     all_neg(x)                      memset(x,-1,sizeof(x))
#define     all_1(x)                        memset(x,1,sizeof(x))
//I/O : 
#define     Faster                          ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 
#define     Read(x)                         freopen(x,"r",stdin)
#define     Write(x)                        freopen (x,"w",stdout)
#define     PI                              acos(-1)
#define     take_the_array(x,n)             for(int i=0;i<n;i++){scanf("%d",&x[i]);}
#define     take_the_matrix(x,n,m)          for(int i=0;i<n;i++){for(int j=0;j<m;j++){scanf("%d",&x[i][j]);}}
#define     take_the_vector(x,n)            int o;for(int i=0;i<n;i++){scanf("%d",&o);x.pb(o);};
#define     print_the_array(x,n)            for(int i=0;i<n;i++){printf("%d ",x[i]);}printf("\n");
#define     print_the_vector(x)             for(auto ii:x){cout<<ii<<" ";}cout<<endl;
#define     print_the_matrix(x,n,m)         for(int i=0;i<n;i++){for(int j=0;j<m;j++){printf("%d ",x[i][j]);}printf("\n");}
#define     int_in(x)                       scanf("%d",&x);
#define     int_in3(x,y,z)                  scanf("%d %d %d",&x,&y,&z);
#define     int_in2(x,y)                    scanf("%d %d",&x,&y);
#define     ll_in(x)                        scanf("%lld",&x);
#define     char_in(x)                      scanf("%c",&x);
#define     str_in(x)                       scanf("%s",&x);
#define     int_out(x)                      printf("%d",x);
#define     ll_out(x)                       printf("%lld",x);
#define     char_out(x)                     printf("%c",x);
#define     str_out(x)                      printf("%s",x);
#define     YES                             printf("YES\n");
#define     Yes                             printf("Yes\n");
#define     NO                              printf("NO\n");
#define     No                              printf("No\n");
#define     nl                              printf("\n");
//extras :
#define     e5                              int main()
#define     checkmate                       return 0;
#define     INF                             0x3f
#define     in_range(x,y)                   for(int i=x;i<=y;i++)
#define     in_range_back(x,y)              for(int i=y;i>=x;i--)
#define     in_range_nested(x,y)            for(int j=x;j<=y;j++)


//..............................................Let's Start with e5, shan't we.?......................................
struct final_list{
    vi data;
};
vector<final_list>ans;

e5{
    int t;int_in(t)
    while(t--){
        int n;int_in(n)
        int a[n];
        ans.clear();
        take_the_array(a,n);
        vi temp;
        in_range(0,n-1){
            if(temp.empty()){
                temp.pb(a[i]);
            }
            else{
                if(a[i]==1){
                    temp.pb(a[i]);
                }
                else{
                    int curr=a[i];
                    while(!temp.empty()){
                        int last=temp.back();
                        temp.pop_back();
                        if(last==curr-1){
                            temp.pb(curr);
                            break;
                        }
                    }
                    if(temp.empty()){
                        temp.pb(curr);
                    }
                }
            }
            ans.pb({temp});
        }
        for(auto curr:ans){
            int sz=curr.data.size(),turn=1;
            for(auto x:curr.data){
                int_out(x);
                if(turn<sz){
                    char_out('.');
                }
                else{nl}
                turn++;
            }
        }
    }
    checkmate
}