Jums duota lygiai n vienodų degtukų. Jūsų užduotis – naudojant visus šiuos degtukus sudaryti teigiamą sveikąjį skaičių. Kiekvienam skaitmeniui nuo 0 iki 9 sudaryti reikia tam tikro kiekio degtukų.
Taisyklės:
Privalote panaudoti lygiai n degtukų.
Gautas skaičius turi būti teigiamas sveikasis skaičius (be nulių skaičiaus pradžioje).
Jei neįmanoma sudaryti jokio teigiamo sveikojo skaičiaus, išveskite -1.
Raskite mažiausią įmanomą skaičių, kurį galima sudaryti.
Input
Pirmoje eilutėje pateiktas sveikasis skaičius T (1 \le T \le 10^3) – testų rinkinių skaičius.
Kiekvieną testų rinkinį sudaro vienas sveikasis skaičius n (1 \le n \le 10^5), nurodantis turimų degtukų kiekį.
Output
Kiekvienam testų rinkiniui išveskite mažiausią teigiamą sveikąjį skaičių, kurį galima sudaryti panaudojant visus n degtukų. Kadangi skaičius gali būti labai didelis, išveskite jį kaip simbolių eilutę. Jei toks skaičius neegzistuoja, išveskite -1.
Examples
| standard input | standard output |
|---|
| 3
2
6
15
| 1
6
108
|
Note
Skaitmenims reikalingas degtukų kiekis nustatomas pagal standartinį septynių segmentų indikatorių:
2 degtukai: 1
3 degtukai: 7
4 degtukai: 4
5 degtukai: 2, 3, 5
6 degtukai: 0, 6, 9
7 degtukai: 8