[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 поени: без додатних огранїченьох.