[old] Abakus 2

A középiskolai programozási versenyek bizottsága majdnem egy évtizeddel ezelőtt megállapította, hogy: „Az ókori babilóniaiak az Abakusz egy változatát használták bonyolult matematikai számításokhoz...”. Most épp megtaláltátok ezt az Abakuszt (logikus, hogy 3000 m tengerszint feletti magasságban, a bizottság fészkében, ahol a régi versenyfeladatokat őrzik).

Sokan nem tudják, de az Abakusz egy feladatot is elétek tár. Ha megoldjátok a feladatokat, jutalmul az Abakusz visszarepít benneteket a távoli 2016-ba (ami nagyon jó, mert ismeritek az összes korábbi verseny feladatának megoldását).

Az Abakusz ki tudja számolni egy adott természetes szám számjegyeinek szorzatát (például a 123 számra az Abakusz a 6=1\cdot 2\cdot 3 értéket adja eredményül. Hasonlóan, az 1024 esetén az Abakusz 0=1\cdot 0\cdot 2\cdot 4 értéket adja megoldásként). A feladatotok az, hogy egy adott n számra meghatározzátok, hány különböző értéket adna vissza az Abakusz, ha az 1,2,\ldots,n számokat adnánk meg neki.

Ahhoz, hogy teljesen biztosak legyetek a megoldásotokban, T lekérdezésre kell választ adnotok, ahol minden lekérdezésben kaptok egy n számot, és minden egyes lekérdezésre meg kell oldanotok a leírt feladatot. Ha hibáztok, az Abakusz 2006-ba küld vissza 2016 helyett, viszont azokat a feladatokat még nem gyakoroltátok...

Bemenet leírása

A szabványos bemenet első sorában egy T természetes szám szerepel, amely a lekérdezések számát jelöli.

A szabványos bemenet következő T sorának mindegyikében egy-egy n természetes szám található.

Kimenet leírása

Mindegyik T lekérdezésre a szabványos kimenet egy-egy sorába egy egész számot kell kiírni – a különböző értékek számát, amelyeket az Abakusz kiír a megadott 1,2,\ldots,n számokra.

1. példa

Bemenet

3
1
10
13

Kimenet

1
10
10

A példa magyarázata

• Az első lekérdezésben az Abakusznak csak az 1 számot adjuk meg, a számjegyek szorzata 1, és ez az egyetlen érték, amit visszaad. A kiírt érték tehát 1.

• A második lekérdezésben az Abakusznak az 1,2,3,4,5,6,7,8,9,10 számokat adjuk meg, ezek számjegyszorzatai sorban 1,2,3,4,5,6,7,8,9,0 – itt 10 különböző érték van, ezért 10-et írunk ki.

• A harmadik lekérdezésben az Abakusznak az 1,2,3,4,5,6,7,8,9,10,11,12,13 számokat adjuk meg, a számjegyszorzatok pedig sorban 1,2,3,4,5,6,7,8,9,0,1,2,3 – itt ismét 10 különböző érték van, ezért 10-et írunk ki. (Megfigyelhető, hogy az utolsó három visszaadott szám ismétlődés, ezért nem 13 a válasz.)

  
  

2. példa

Bemenet

1
111

Kimenet

37

Korlátozások

• 1 \leq T \leq 200.000
• 1 \leq n \leq 10^{18}

A tesztpéldák nyolc diszjunkt csoportba vannak sorolva:

• Az 5 pontot érő tesztpéldákban: érvényes, hogy n \leq 10
• Az 5 pontot érő tesztpéldákban: érvényes, hogy n \leq 100.
• A 10 pontot érő tesztpéldákban: érvényes, hogy n \leq 10.000.
• A 10 pontot érő tesztpéldákban: érvényes, hogy n \leq 1.000.000.
• A 10 pontot érő tesztpéldákban: érvényes, hogy n \leq 10^9.
• A 10 pontot érő tesztpéldákban: érvényes, hogy n \leq 10^{12}.
• A 10 pontot érő tesztpéldákban: érvényes, hogy T = 1.
• A 10 pontot érő tesztpéldákban: érvényes, hogy T \leq 1.000.
• A 30 pontot érő tesztpéldákban: nincsenek további korlátozások.