🏡 index : github.com/captn3m0/codechef.git

---
category_name: school
problem_code: LISDIGIT
problem_name: 'Digit Longest Increasing Subsequences 2'
languages_supported:
    - ADA
    - ASM
    - BASH
    - BF
    - C
    - 'C99 strict'
    - CAML
    - CLOJ
    - CLPS
    - 'CPP 4.3.2'
    - 'CPP 4.9.2'
    - CPP14
    - CS2
    - D
    - ERL
    - FORT
    - FS
    - GO
    - HASK
    - ICK
    - ICON
    - JAVA
    - JS
    - 'LISP clisp'
    - 'LISP sbcl'
    - LUA
    - NEM
    - NICE
    - NODEJS
    - 'PAS fpc'
    - 'PAS gpc'
    - PERL
    - PERL6
    - PHP
    - PIKE
    - PRLG
    - PYPY
    - PYTH
    - 'PYTH 3.4'
    - RUBY
    - SCALA
    - 'SCM chicken'
    - 'SCM guile'
    - 'SCM qobi'
    - ST
    - TCL
    - TEXT
    - WSPC
max_timelimit: '3'
source_sizelimit: '50000'
problem_author: alex_2oo8
problem_tester: kingofnumbers
date_added: 21-01-2017
tags:
    - alex_2oo8
    - cakewalk
    - constructive
    - cook78
    - lis
editorial_url: 'https://discuss.codechef.com/problems/LISDIGIT'
time:
    view_start_date: 1485109800
    submit_start_date: 1485109800
    visible_start_date: 1485109800
    end_date: 1735669800
    current: 1492506700
layout: problem
---
All submissions for this problem are available.###  Read problems statements in [Mandarin Chinese](http://www.codechef.com/download/translated/COOK78/mandarin/LISDIGIT.pdf), [Russian](http://www.codechef.com/download/translated/COOK78/russian/LISDIGIT.pdf) and [Vietnamese](http://www.codechef.com/download/translated/COOK78/vietnamese/LISDIGIT.pdf) as well.

Recently Chef learned about [Longest Increasing Subsequence](https://en.wikipedia.org/wiki/Longest_increasing_subsequence). To be precise, he means longest **strictly** increasing subsequence, when he talks of longest increasing subsequence. To check his understanding, he took his favorite **n**-digit number and for each of its **n** digits, he computed the length of the longest increasing subsequence of digits ending with that digit. Then he stored these lengths in an array named **LIS**.

For example, let us say that Chef's favourite **4**-digit number is **1531**, then the **LIS** array would be **\[1, 2, 2, 1\]**. The length of longest increasing subsequence ending at first digit is **1** (the digit **1** itself) and at the second digit is **2** (**\[1, 5\]**), at third digit is also **2** (**\[1, 3\]**), and at the **4**th digit is **1** (the digit **1** itself).

Now Chef wants to give you a challenge. He has a valid **LIS** array with him, and wants you to find any **n**-digit number having exactly the same **LIS** array? You are guaranteed that Chef's **LIS** array is valid, i.e. there exists at least one **n**-digit number corresponding to the given **LIS** array.

### Input

The first line of the input contains an integer **T** denoting the number of test cases.

For each test case, the first line contains an integer **n** denoting the number of digits in Chef's favourite number.

The second line will contain **n** space separated integers denoting **LIS** array, i.e. **LIS1, LIS2, ..., LISn**.

### Output

For each test case, output a single **n**-digit number (without leading zeroes) having exactly the given **LIS** array. If there are multiple **n**-digit numbers satisfying this requirement, any of them will be accepted.

### Constraints

- **1** ≤ **T** ≤ **30 000**
- **1** ≤ **n** ≤ **9**
- It is guaranteed that at least one **n**-digit number having the given **LIS** array exists

### Example

<pre><b>Input:</b>
5
1 
1
2 
1 2
2 
1 1
4
1 2 2 1
7 
1 2 2 1 3 2 4

<b>Output:</b>
7
36
54
1531
1730418
</pre>### Explanation

**Example case 1.** All one-digit numbers have the same **LIS** array, so any answer from 0 to **9** will be accepted.

**Example cases 2 & 3.** For a two digit number we always have **LIS1 = 1**, but the value of **LIS2** depends on whether the first digit is strictly less than the second one. If this is the case (like for number **36**), **LIS2 = 2**, otherwise (like for numbers **54** or **77**) the values of **LIS2** is **1**.

**Example case 4.** This has already been explained in the problem statement.

**Example case 5.** **7**-digit number **1730418** has **LIS** array **\[1, 2, 2, 1, 3, 2, 4\]**:

  index LIS length   1 **1**730418 1   2 **17**30418 2   3 **1**7**3**0418 2   4 1730418 1   5 **1**7**3**0**4**18 3   6 17304**1**8 2   7 **1**7**3**0**4**1**8** 4