[old] Abakus 2

Comisia pentru olimpiadele de programare destinate elevilor de liceu a constatat, cu aproape un deceniu în urmă: „Vechii babilonieni foloseau o variantă a dispozitivului numit Abac pentru calcule matematice complicate…”. Dumneavoastră ați descoperit acum acest Abac (în mod logic, l-ați găsit la o altitudine de 3000 m, într-un loc ascuns al comisiei, unde se păstrează olimpiadele anterioare).

Ceea ce este mai puțin cunoscut este faptul că Abacul oferă și o sarcină. Ca recompensă pentru rezolvarea acestei sarcini, Abacul vă va întoarce în îndepărtatul an 2016 (ceea ce este foarte bine, deoarece cunoașteți soluțiile tuturor problemelor de la olimpiadele anterioare).

Abacul poate calcula, pentru un număr natural dat, produsul cifrelor sale (de exemplu, pentru numărul 123, Abacul ar returna valoarea 6=1\cdot 2\cdot 3. În mod similar, pentru valoarea 1024, Abacul ar returna valoarea 0=1\cdot 0\cdot 2\cdot 4). Sarcina dumneavoastră este ca, pentru numărul dat n, să calculați câte valori diferite ar returna Abacul dacă i s-ar introduce numerele 1,2,\ldots, n.

Pentru a fi pe deplin siguri de soluția dumneavoastră, trebuie să răspundeți la T interogări, unde în fiecare interogare primiți un număr n, iar pentru fiecare interogare rezolvați sarcina descrisă. Dacă greșiți, Abacul vă va întoarce în anul 2006 în loc de 2016, iar acele probleme nu le-ați mai exersat…

Descrierea intrării

Pe prima linie a intrării standard este dat un număr natural T, numărul de interogări.

În următoarele T linii ale intrării standard, se află câte un număr natural – n.

Descrierea ieșirii

Pentru fiecare dintre cele T interogări trebuie afișată câte o linie la ieșirea standard, care să conțină un singur număr întreg – numărul de valori diferite pe care le va afișa Abacul pentru numerele introduse 1, 2, \ldots, n.

Exemplul 1

Intrare

3

1

10

13

Ieșire

1

10

10

Explicație

• În prima interogare, îi dăm Abacului doar numărul 1; produsul cifrelor sale este egal cu 1 și aceasta este singura valoare pe care o va returna Abacul. Afișarea este, așadar, 1.

• În a doua interogare, îi dăm Abacului numerele 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, iar produsele cifrelor acestor numere sunt, în ordine, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 – aici avem 10 valori diferite, deci afișăm 10.

• În a treia interogare, îi dăm Abacului numerele 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, iar produsele cifrelor acestor numere sunt, în ordine, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3 – și aici avem din nou 10 valori diferite, deci afișăm 10. (Observăm că ultimele trei valori returnate sunt duplicate, așadar afișarea nu este 13.)

Exemplul 2

Intrare

1

111

Ieșire

37

Restricții

• 1 \leq T \leq 200.000

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

Exemplele de test sunt împărțite în 8 grupuri disjuncte:

• În testele care valorează de 5 puncte: este valabil n \leq 10.

• În testele care valorează 5 puncte: este valabil n \leq 100.

• În testele care valorează 10 puncte: este valabil n \leq 10.000.

• În testele care valorează 10 puncte: este valabil n \leq 1.000.000.

• În testele care valorează 10 puncte: este valabil n \leq 10^9.

• În testele care valorează 10 puncte: este valabil n \leq 10^{12}.

• În testele care valorează 10 puncte: este valabil T = 1.

• În testele care valorează 10 puncte: este valabil T \leq 1.000.

• În testele care valorează 30 puncte: fără restricții suplimentare.