4. Ondrej odpúšťa

,,Vyberme si nejaké náhodné číslo, napríklad päť. Hm, to je málo, päťdesiat päť,’’ začal Ondrej Demáček vysvetľovanie nového zaujímavého algoritmu na hodine informatiky. Táto programátorská legenda už celé desaťročia nezlyhala v upútavaní pozornosti svojich študentov.

Až na Zaja. Zajo ten algoritmus už totiž poznal a tak sa mimoriadne nudil. Hojdal sa na stoličke, šepkal spolužiakom trápne vtipy, hádzal zožmolené kusy papiera do koša za dverami triedy, skrátka, robil neporiadok. Každému by z toho praskli nervy. Aj Demáčkovi.

,,Zajo! Vyrušuješ! Tu máš prázdny zošit, mazaj za dvere a napíš doňho všetky prirodzené čísla od jedna po milión.’’

Zajo sklopil uši, zobral zošit do ruky a vyšiel za dvere. Spoza dverí začul ešte Demáčka: ,,Kto túto úlohu vyrieši ako prvý, dostane celú túto tabuľku čokolády’’.

,,Ale no tak,’’ pomyslel si Zajo. ,,Zaručene by som to vyriešil prvý. Mohol som mať čokoládu. Keby ten starý… musím sa mu nejako pomstiť… už viem! Keď už má tak rád to číslo päť, v tomto zošite ho nenájde. Napíšem sem všetky čísla od jedna po milión, okrem tých, ktoré obsahujú cifru päť. Pche, a načo sa zastavovať na milióne? Však ja mu ukážem!’’

S novým nadšením sa Zajo pustil do práce.

Úloha

Zajo do svojho zošita píše za sebou prirodzené čísla od 1. Demáček mu dal za úlohu len do milión, Zajo sa však rozhodol, že sa nikdy nezastaví v písaní. Zajo pri tom vynecháva všetky čísla, ktoré obsahujú cifru 5.

Začiatok jeho zošita teda vyzerá takto:

1 2 3 4 6 7 8 9 10 11 12 13 14 16 17 18 19 20 21 22 23 24 26 27 28 29 ...

A keď prelistujeme zopár strán ďalej, tak to vyzerá takto:

... 491 492 493 494 496 497 498 499 600 601 602 603 604 606 ...

Dostanete číslo \(k\). Vašou úlohou je zistiť hodnotu \(k\)-tej cifry napísanej v Zajovom zošite. Číslujeme od nuly.

Formát vstupu

Každý testovací vstup obsahuje otázky na niekoľko cifier v Zajovom zošite. Na prvom riadku vstupu sa nachádza počet týchto otázok, celé číslo \(n\). Nasleduje \(n\) riadkov. V \(i\)-tom z nich sa nachádza celé číslo \(k_i\) – číslo cifry, ktorá nás zaujíma v \(i\)-tej otázke. Platí \(1 \leq n \leq 10^5\) a \(0 \leq k_i \leq 10^{18}\).

Sú 4 sady testovacích vstupov. Pre jednotlivé sady navyše platia nasledovné obmedzenia:

Pozor! Druhá a tretia sada majú špeciálne limity na \(k_i\). Ak aj nevyriešite úlohu optimálne, za kreatívne vyriešenie druhej a tretej sady a následné popísanie vášho postupu môžete získať aj nejaké body za popis.

Formát výstupu

Vypíšte \(n\) riadkov, pričom na \(i\)-tom riadku má byť hodnota \(k_i\)-tej cifry v Zajovom zošite.

Príklady

Input:

5
0
1
4
17
19

Output:

1
2
6
4
6