[old] Abakus 2

Комисија за средњошколска такмичења из програмирања је пре скоро целе деценије констатовала: "Стари Вавилонци су користили једну варијанту направе Абакус за компликована математичка израчунавања...". Ви сте сада пронашли тај Абакус (логично, пронашли сте га на 3000м надморске висине у комисијском гнезду, где се чувају стара такмичења).

Оно што је мало познато, јесте да Абакус нуди и задатак. Као награду за решавање задатка, Абакус ће Вас вратити у давну 2016-ту (што је јако добро, јер знате решења свих задатака са прошлих такмичења).

Абакус може да за задати природан број да израчуна производ његових цифара (на пример, за број 123, Абакус би вратио вредност 6=1\cdot 2\cdot 3. Слично, за вредност 1024, Абакус би вратио вредност 0=1\cdot 0\cdot 2\cdot 4). Ваш задатак је да за задат број n израчунате колико различитих вредности би Абакус вратио уколико би му се унели бројеви 1,2,\ldots,n.

Како бисте били сасвим сигурни у Ваше решење, морате да одговорите на T упита, где у сваком упиту добијете број n и за сваки упит решавате описани задатак. Ако погрешите, Абакус Вас враћа у 2006-ту уместо 2016-те, а те задатке већ нисте увежбали...

Опис улаза

У првој линији стандардног улаза дат је природан број T, број упита.

У наредних T линија стандардног улаза, налази се по један природан број - n.

Опис излаза

За сваки од T упита треба исписати једну линију стандардог излаза која садржи један цео број - број различитих вредности које ће Абакус исписати за унете бројеве 1,2,\ldots,n.

Пример 1

Улаз

3
1
10
13

Излаз

1
10
10

Објашњење

• У првом упиту, Абакусу дајемо само број 1, његов производ цифара једнак је 1 и то је једина вредност коју ће Абакус вратити. Испис је онда 1.
• У другом упиту, Абакусу дајемо бројеве 1,2,3,4,5,6,7,8,9,10 и производи цифара ових бројева су редом 1,2,3,4,5,6,7,8,9,0 - и ту имамо 10 различитих вредности, па и исписујемо 10.
• У трећем упиту, Абакусу дајемо бројеве 1,2,3,4,5,6,7,8,9,10,11,12,13 и производи цифара ових бројева су редом 1,2,3,4,5,6,7,8,9,0,1,2,3 - и ту имамо поново 10 различитих вредности, па и исписујемо 10. (Приметимо да су последња три враћена броја дупликати, па испис није 13).

Пример 2

Улаз

1
111

Излаз

37

Ограничења

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

Тест примери су подељени у 8 дисјунктних група:

• У тестовима вредним 5 поена: важи n \leq 10
• У тестовима вредним 5 поена: важи n \leq 100.
• У тестовима вредним 10 поена: важи n \leq 10.000.
• У тестовима вредним 10 поена: важи n \leq 1.000.000.
• У тестовима вредним 10 поена: важи n \leq 10^9.
• У тестовима вредним 10 поена: важи n \leq 10^{12}.
• У тестовима вредним 10 поена: важи T = 1.
• У тестовима вредним 10 поена: важи T \leq 1.000.
• У тестовима вредним 30 поена: без додатних ограничења.