[ol2] Abakus 2

Abakus

Komisia pre stredoškolské súťaže v programovaní už takmer pred celým desaťročím skonštatovala: "Starí Babylončania používali jednu verziu zariadenia Abakus na zložité matematické výpočty." Teraz ste tento Abakus našli (logicky vo výške 3000 m n. m. v komisnom hniezde, kde sa uchovávajú staré súťaže).

Menej známe však je, že Abakus ponúka aj úlohu. Ako odmenu za jej vyriešenie vás Abakus vráti do roku 2016 (čo je výborné, pretože poznáte riešenia všetkých úloh z minulých súťaží).

Abakus vie pre zadané prirodzené číslo vypočítať súčin jeho číslic (napríklad pre číslo 123 je výsledok 6 = 1·2·3, pre číslo 1024 je výsledok 0 = 1·0·2·4). Vašou úlohou je pre dané číslo n určiť, koľko rôznych hodnôt Abakus vráti, ak mu zadáme čísla 1, 2, ..., n. Aby ste si boli úplne istí riešením, musíte odpovedať na T dopytov. V každom dopyte dostanete číslo n a riešite uvedenú úlohu. Ak sa pomýlite, Abakus vás vráti do roku 2006 namiesto 2016.

Vstup: V prvom riadku je prirodzené číslo T – počet dopytov. V nasledujúcich T riadkoch je po jednom prirodzenom čísle n.

Výstup: Pre každý dopyt vypíšte jedno celé číslo – počet rôznych hodnôt, ktoré Abakus vráti pre čísla 1 až n.

Obmedzenia: 1 ≤ T ≤ 200 000 1 ≤ n ≤ 10^18