#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <bitset>
#include <stack>
#include <string>
#include <cstring>
#include <cassert>
#include <limits.h>

using namespace std;

typedef unsigned long long LL;
typedef long double LD;

typedef vector<int> VI;
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(VAR(i,a);i<=(b);++i)
#define FORD(i,a,b) for(VAR(i,a);i>=(b);--i)
#define FORE(a,b) for(VAR(a,(b).begin());a!=(b).end();++a)
#define VAR(a,b) __typeof(b) a=(b)
#define SIZE(a) ((int)((a).size()))
#define ALL(x) (x).begin(),(x).end()
#define CLR(x,a) memset(x,a,sizeof(x))
#define ZERO(x) memset(x,0,sizeof(x))
#define S(t,i) scanf("%" ## t, &i)
#define SI(i) scanf("%d", &i)

const int precomputed=999;
int cyfry[22];
int cyfry_tmp[22];
LL c[10], wyniki[10];
LL mapping[precomputed+111];

const int max_precomputed_results=19;
LL precomputed_results[max_precomputed_results][9] = {{1,1,1,1,1,1,1,1,1},
    {1,8,2,9,6,13,2,22,3},
    {1,68,3,55,33,141,3,138,6},
    {1,466,4,214,132,1017,4,889,10},
    {1,2670,5,615,435,5671,5,4921,15},
    {1,13460,6,1451,1466,36695,6,26687,21},
    {1,69420,7,3829,5341,274919,7,154539,28},
    {1,417722,8,60180,18656,1905346,8,870270,36},
    {1,3025242,9,939045,58029,11961897,9,4437621,45},
    {1,21873040,10,8732485,159430,70484777,10,20367762,55},
    {1,136901413,11,56961531,392601,393138130,11,86589471,66},
    {1,722201372,12,289887214,882036,2099243511,12,388661761,78},
    {1,3271729383,13,1229099287,1836159,11182203514,13,2366418106,91},
    {1,13114173697,14,4756606869,3586506,61491912211,14,18602433227,105},
    {1,48104723380,15,24218431805,6638885,342906589613,15,142978182070,120},
    {1,167526488628,16,233925901576,11738656,1849155959180,16,952075901928,136},
    {1,574289772576,17,2661527233449,19952441,9348828582989,17,5434361620523,153},
    {1,1988721563904,18,25685325408201,32768742,44293571012946,18,27064481351856,171}};

const int max_memorized_results=18*1000*10*2*10;
LL memorized_results[max_memorized_results][10];
unordered_map<LL,LL*> memorized_results_map;
LL hash_memorized_result(int length, LL prefix) {
    return (length+prefix*19);
}
unordered_map<LL,LL*> memorized_results_map1;
LL hash_memorized_result1(int length, LL prefix) {
    return (length+prefix*19);
}

int memorized_results_count=0;
LL *getNewMemorizedResult(){
    //assert(memorized_results_count<max_memorized_results-10);
    return memorized_results[memorized_results_count++];
}

LL to_memorize[11][10]={
    // {0,0,0,0,0,105,0,0,0,0,320LL},
    // {0,0,0,0,0,1092,0,0,0,0,358LL},
    // {0,0,0,0,0,1274,0,0,0,0,130LL},
    // {0,0,0,0,0,1274,0,0,0,0,73LL},
    // {0,0,0,0,0,1275,0,0,0,0,187LL},
    // {0,0,0,0,0,1365,0,0,0,0,36LL},
    // {0,0,0,0,0,14,0,0,0,0,244LL},
    // {0,0,0,0,0,14,0,0,0,0,301LL},
    // {0,0,0,0,0,143627,0,0,0,0,358LL},
    // {0,0,0,0,0,1514113,0,0,0,0,168LL},
    // {0,0,0,0,0,160735,0,0,0,0,415LL},
    // {0,0,0,0,0,182,0,0,0,0,472LL},
    // {0,0,0,0,0,21308,0,0,0,0,529LL},
    // {0,0,0,0,0,214756,0,0,0,0,55LL},
    // {0,0,0,0,0,2330531,0,0,0,0,111LL},
    // {0,0,0,0,0,246046,0,0,0,0,74LL},
    // {0,0,0,0,0,2,8,8,6,0,2409LL},
    // {0,0,0,0,0,28953,0,0,0,0,93LL},
    // {0,0,0,0,0,312321,0,0,0,0,320LL},
    // {0,0,0,0,0,35322,0,0,0,0,92LL},
    // {0,0,0,0,0,365793,0,0,0,0,472LL},
    // {0,0,0,0,0,37338,0,0,0,0,168LL},
    // {0,0,0,0,0,4368,0,0,0,0,244LL},
    // {0,0,0,0,0,45285,0,0,0,0,112LL},
    // {0,0,0,0,0,49365,0,0,0,0,131LL},
    // {0,0,0,0,0,53475,0,0,0,0,150LL},
    // {0,0,0,0,0,546,0,0,0,0,320LL},
    // {0,0,0,0,0,560,0,0,0,0,472LL},
    // {0,0,0,0,0,581337,0,0,0,0,548LL},
    // {0,0,0,0,0,6,0,6,8,0,927LL},
    // {0,0,0,0,0,63552,0,0,0,0,624LL},
    // {0,0,0,0,0,665,0,0,0,0,169LL},
    // {0,0,0,0,0,680,0,0,0,0,188LL},
    // {0,0,0,0,0,7190,0,0,0,0,624LL},
    // {0,0,0,0,0,7204,0,0,0,0,700LL},
    // {0,0,0,0,0,7295,0,0,0,0,111LL},
    // {0,0,0,0,0,92,0,0,0,0,301LL},
    // {0,0,0,0,0,954551,0,0,0,0,35LL},
    // {0,0,0,0,0,9571,0,0,0,0,54LL},
    // {0,0,0,0,0,9661,0,0,0,0,73LL},
    // {0,0,0,0,0,9676,0,0,0,0,92LL},
    // {0,0,0,2,4,6,8,0,2,4,813LL},
    // {0,0,0,4,6,8,0,0,6,4,2808LL},
    // {0,0,0,5,0,0,0,5,0,0,4632LL},
    // {0,0,0,5,0,0,0,5,0,0,547LL},
    // {0,0,0,5,0,0,0,5,0,8,1839LL},
    // {0,0,0,5,0,5,0,0,0,5,3606LL},
    // {0,0,0,8,6,8,6,0,6,0,319LL},
    // {0,0,0,9,8,4,8,0,0,8,927LL},
    // {0,0,10025850345LL,0,107573466000LL,0,105152224951LL,0,102312764642LL,0,1384LL},
    // {0,0,1038627513,0,3745595854LL,0,16395960702LL,0,16283287930LL,0,319LL},
    // {0,0,1072765876,0,19487656188LL,0,17523066134LL,0,2981511533LL,0,946LL},
    // {0,0,107723197271LL,0,331483705352LL,0,1393872382200LL,0,886249374736LL,0,491LL},
    // {0,0,1099128215LL,0,1,0,52268837413LL,0,43365901305LL,0,91LL},
    // {0,0,11087644490LL,0,30658069785LL,0,193542768631LL,0,93158098688LL,0,1042LL},
    // {0,0,111172334,0,0,0,4612505171LL,0,5294014726LL,0,1041LL},
    // {0,0,11147593903LL,0,80263703520LL,0,127795276816LL,0,118295477534LL,0,1232LL},
    // {0,0,1129765,0,5206452342LL,0,1412089604LL,0,501026344,0,547LL},
    // {0,0,1138473182LL,0,2537162733LL,0,28095365585LL,0,8839343164LL,0,547LL},
    // {0,0,116064130,0,5819868054LL,0,6692950488LL,0,6908957510LL,0,1212LL},
    // {0,0,11763752,0,2998607612LL,0,4031638534LL,0,1427258560LL,0,471LL},
    // {0,0,118324717262LL,0,3289671369520LL,0,4145913647648LL,0,2342037756314LL,0,54LL},
    // {0,0,1186364557LL,0,0,7112,14440580560LL,0,20727156192LL,0,699LL},
    // {0,0,1186764661LL,0,49811541780LL,0,59438771413LL,0,54101273360LL,0,72LL},
    // {0,0,1237209806LL,0,2043871207LL,0,23198257033LL,0,14701927514LL,0,1383LL},
    // {0,0,1254344,0,1680901313LL,0,2357188785LL,0,321884836,0,167LL},
    // {0,0,126214466,0,1268735833LL,14196,18502626767LL,0,3548025392LL,0,357LL},
    // {0,0,1282660150LL,0,19031037496LL,106940,141467007195LL,0,21274566818LL,0,167LL},
    // {0,0,1304734511LL,0,5335259944LL,0,20886601778LL,0,14372392413LL,0,927LL},
    // {0,0,131682930,0,13853741265LL,0,46909135245LL,0,10098305925LL,0,300LL},
    // {0,0,1363964070LL,0,22817033330LL,0,16524482989LL,0,4297907719LL,0,148LL},
    // {0,0,139357195,0,52253777940LL,0,18949013045LL,0,9599445328LL,0,281LL},
    // {0,0,14399662504LL,0,270034311040LL,0,524925949893LL,0,436715374052LL,0,149LL},
    // {0,0,14607152,0,879092032,2184,12648043408LL,0,930083441,0,471LL},
    // {0,0,146291082,0,3898020126LL,0,13884758446LL,0,3488826098LL,0,1041LL},
    // {0,0,15395835,0,25213519695LL,0,18701423345LL,0,2865834401LL,0,243LL},
    // {0,0,1558739,0,0,182,3736765942LL,0,573981149,0,547LL},
    // {0,0,15803521564LL,0,234139390192LL,795680,925632437780LL,0,263843480296LL,1,814LL},
    // {0,0,1595144895LL,0,14633711835LL,101130,115161220472LL,0,40921531516LL,0,72LL},
    // {0,0,160145819015LL,0,1426962514565LL,3993521,5009166641964LL,1,3501256072435LL,0,92LL},
    // {0,0,1626564212LL,0,24430916510LL,0,15586060868LL,0,6414394441LL,0,699LL},
    // {0,0,1659556056LL,0,221659860240LL,0,381334605556LL,0,73851220214LL,0,814LL},
    // {0,0,16743673425LL,0,151142490056LL,657120,735823586056LL,0,401141449922LL,0,681LL},
    // {0,0,16912896,0,0,0,2511423278LL,0,1823254083LL,0,1079LL},
    // {0,0,1749763,0,1501227728LL,0,5636991752LL,0,145276742,0,243LL},
    // {0,0,1826050499LL,0,23953831902LL,0,15052278878LL,0,9134191339LL,0,129LL},
    // {0,0,18281639152LL,0,606793867696LL,0,432142761172LL,0,355336465453LL,0,472LL},
    // {0,0,18366321393LL,1,21015375585LL,2023260,261504612384LL,0,97469338311LL,15,700LL},
    // {0,0,1840486,0,2106653640LL,0,31239815463LL,0,83059158,0,623LL},
    // {0,0,192023780,0,13186380480LL,16380,95900244577LL,0,5832283109LL,0,357LL},
    // {0,0,19244786,0,10870580812LL,0,7276065888LL,0,3418781730LL,0,1554LL},
    // {0,0,1941948386LL,0,21514474982LL,0,15161948659LL,0,12160766982LL,0,870LL},
    // {0,0,19617689,0,0,0,3598995323LL,0,1152432827LL,0,813LL},
    // {0,0,1963761996LL,0,1683101448LL,325780,37753002938LL,0,9151615165LL,1,281LL},
    // {0,0,19811642068LL,0,38273670076LL,0,208454487722LL,0,139549700370LL,0,187LL},
    // {0,0,19880875,0,2868665800LL,0,9250007118LL,0,968677830,0,281LL},
    // {0,0,19918470,0,6552147420LL,1365,58631848405LL,0,935534590,0,319LL},
    // {0,0,2004923011LL,0,13345506174LL,0,18017525047LL,0,17737383861LL,0,300LL},
    // {0,0,2039511462LL,0,2551577886LL,0,22308377407LL,0,19946119557LL,0,813LL},
    // {0,0,204355515,0,0,7280,12091607571LL,0,7299163809LL,0,1383LL},
    // {0,0,2083627106LL,0,3488208920LL,0,28249966773LL,0,14780633259LL,0,813LL},
    // {0,0,210110802,0,44979114180LL,0,33391259688LL,0,12148761555LL,0,243LL},
    // {0,0,211536083,0,64365161445LL,0,42229268806LL,0,25895132915LL,0,148LL},
    // {0,0,2128783930LL,0,9279616346LL,0,21129597714LL,0,19678305038LL,0,490LL},
    // {0,0,2130310,0,6351120048LL,0,1582015267LL,0,1370154968LL,0,243LL},
    // {0,0,223860014,0,7171564400LL,0,9527764771LL,0,9483991531LL,0,623LL},
    // {0,0,224435,0,64030148,0,4296907993LL,0,11177166,0,1079LL},
    // {0,0,2249591177LL,0,1401024457LL,283556,31933827422LL,0,16831322263LL,0,927LL},
    // {0,0,2302451415LL,0,15,49140,81606584416LL,0,65293383910LL,0,547LL},
    // {0,0,23273068,0,10629064628LL,0,1578907463LL,0,1239216993LL,0,243LL},
    // {0,0,236438712690LL,0,5518031810925LL,0,3833552629569LL,0,3169118025665LL,0,187LL},
    // {0,0,23986901781LL,0,479845606496LL,0,631279381712LL,0,429104142628LL,0,358LL},
    // {0,0,24662638,0,5074263194LL,0,3669629548LL,0,2986039238LL,0,167LL},
    // {0,0,253162,0,2071277208LL,0,1458022804LL,0,93187640,0,927LL},
    // {0,0,263699501,0,8732579856LL,0,8602265246LL,0,6786957634LL,0,680LL},
    // {0,0,2665351253LL,0,39424029645LL,0,80541662695LL,0,75103072478LL,0,34LL},
    // {0,0,26990783,0,10091581500LL,0,1843627942LL,0,1602221609LL,0,53LL},
    // {0,0,2730,0,140443576,0,4144699559LL,0,2730,0,813LL},
    // {0,0,274584506,0,0,0,6886562151LL,0,9211974542LL,0,623LL},
    // {0,0,277014857,0,2553157698LL,0,20785028460LL,0,3934102487LL,0,699LL},
    // {0,0,2806760684LL,0,210,142324,29197525685LL,0,27031098746LL,0,91LL},
    // {0,0,281240730,0,10969059466LL,19110,77276328785LL,0,14026186520LL,0,167LL},
    // {0,0,282718632,0,4347858515LL,0,10439610770LL,0,9332035727LL,0,870LL},
    // {0,0,287637011553LL,0,4590583290265LL,0,4970554559287LL,0,3925292970721LL,0,168LL},
    // {0,0,29124186,0,0,1274,6933824730LL,0,2502195165LL,0,281LL},
    // {0,0,297325,0,419645408,0,5350780190LL,0,13827996,0,1383LL},
    // {0,0,30163814464LL,0,211174140057LL,0,762828092068LL,0,599481543080LL,0,928LL},
    // {0,0,30615528854LL,0,27720348105LL,0,267931309640LL,0,143337823036LL,0,1080LL},
    // {0,0,3104773220LL,0,0,9570,56112118895LL,0,80568951036LL,0,471LL},
    // {0,0,3118167956LL,0,175504951457LL,153456,618583618907LL,0,91924178462LL,0,947LL},
    // {0,0,3121664,0,1446259178LL,0,4538903761LL,0,481684295,0,699LL},
    // {0,0,31612672,0,0,0,3105989341LL,0,2482619790LL,0,1231LL},
    // {0,0,3257360905LL,0,22248940365LL,0,110256113028LL,0,70468300141LL,0,129LL},
    // {0,0,3274089,0,4582736158LL,0,2801168020LL,0,631259083,0,319LL},
    // {0,0,337974,0,5516355026LL,0,784935452,0,410333287,0,623LL},
    // {0,0,340404064,0,0,1092,7527295505LL,0,10779927433LL,0,1839LL},
    // {0,0,341495973,0,24938283825LL,0,43878904920LL,0,22145041990LL,0,357LL},
    // {0,0,3467777861LL,0,2569780759LL,0,37225384302LL,0,14719738362LL,0,243LL},
    // {0,0,3566556644LL,0,4129671651LL,0,31435810812LL,0,21058407399LL,0,680LL},
    // {0,0,35679377951LL,0,355983047880LL,0,927930426481LL,0,500523071324LL,0,130LL},
    // {0,0,357058520,0,0,0,4302111177LL,0,8495680284LL,0,927LL},
    // {0,0,364006145,0,36161405280LL,0,57779535390LL,0,15016173980LL,0,129LL},
    // {0,0,3764065024LL,0,119950967152LL,142096,474735871800LL,0,162985124507LL,0,1080LL},
    // {0,0,3823725390LL,0,87298020810LL,0,68162976262LL,0,66130951130LL,0,1555LL},
    // {0,0,38354905,0,21693887670LL,0,35019411131LL,0,3635163511LL,0,186LL},
    // {0,0,386546083,0,6120912799LL,0,13418589940LL,0,7674756299LL,0,1079LL},
    // {0,0,387158434419LL,0,3589960401658LL,0,6781742947852LL,0,4699221073136LL,0,149LL},
    // {0,0,392597812,0,100618321440LL,21840,382799109796LL,0,21836203157LL,0,1213LL},
    // {0,0,4,0,0,2,6,2,0,0,3606LL},
    // {0,0,4137289435LL,0,16,0,95457824370LL,0,88845217848LL,0,414LL},
    // {0,0,4264712632LL,0,472746683137LL,0,234921228604LL,0,145035716442LL,0,415LL},
    // {0,0,4279366,0,3483585196LL,0,2072816879LL,0,961825592,0,699LL},
    // {0,0,4355092,0,1154152272LL,0,9454185209LL,0,199142672,0,129LL},
    // {0,0,43684018,0,10239626397LL,0,7442987293LL,0,4932481009LL,0,186LL},
    // {0,0,44175064060LL,0,2039166442570LL,1187824,4001253338345LL,0,1164438370988LL,1,130LL},
    // {0,0,44731235124LL,0,938956789680LL,0,543556341401LL,0,460628092016LL,0,871LL},
    // {0,0,451178014,0,1,0,13556423274LL,0,11550987644LL,0,319LL},
    // {0,0,476289450,0,0,9555,45217068051LL,0,26497948578LL,0,699LL},
    // {0,0,4776600135LL,0,65217877740LL,0,96750138740LL,0,76973149112LL,0,871LL},
    // {0,0,494389325,0,5350913568LL,0,12187121730LL,0,12658248890LL,0,471LL},
    // {0,0,505504394,0,58684799355LL,0,47619727678LL,0,37845352056LL,0,91LL},
    // {0,0,510780949,0,1576138761LL,72450,29094158380LL,0,4378405514LL,0,528LL},
    // {0,0,528225672,0,20725018496LL,0,9151906323LL,0,3289434344LL,0,1231LL},
    // {0,0,53984021,0,0,0,5051874660LL,0,2640238069LL,0,927LL},
    // {0,0,57128708096LL,0,630784474456LL,0,789834040308LL,0,689769385869LL,0,681LL},
    // {0,0,57668744012LL,1,250479263736LL,3332376,1325951950092LL,0,564224427636LL,16,244LL},
    // {0,0,58643574930LL,0,156560419056LL,2571616,1094162376972LL,1,781304162556LL,0,1042LL},
    // {0,0,601533817,0,0,0,10140460971LL,0,14484216152LL,0,471LL},
    // {0,0,6,0,8,4,0,0,0,0,2010LL},
    // {0,0,619472035,0,21779874116LL,0,8156759975LL,0,4653047231LL,0,167LL},
    // {0,0,621176283,0,3042975936LL,0,15963489116LL,0,12046646248LL,0,357LL},
    // {0,0,63008232,0,1809389764LL,0,12152494733LL,0,2767635794LL,0,167LL},
    // {0,0,6364922911LL,0,15654953280LL,438375,161887883932LL,0,88680646935LL,0,167LL},
    // {0,0,6403564386LL,0,324590106516LL,0,370818492472LL,0,304727914804LL,0,282LL},
    // {0,0,645571500,0,37924616730LL,0,44752844201LL,0,37902982860LL,0,91LL},
    // {0,0,648373649,0,4010740748LL,0,19972852018LL,0,8365926402LL,0,1212LL},
    // {0,0,66029964,0,4075803732LL,0,6518387603LL,0,4230982938LL,0,129LL},
    // {0,0,679741673,0,27140846460LL,0,93727739865LL,0,18078619865LL,0,53LL},
    // {0,0,6,8,0,0,0,0,0,0,3093LL},
    // {0,0,68510442,0,0,91,3312084608LL,0,4414692205LL,0,2067LL},
    // {0,0,685857536,0,21072827776LL,0,7519701735LL,0,6404559616LL,0,414LL},
    // {0,0,6907309210LL,0,45644639265LL,0,138570753455LL,0,86221068105LL,0,1213LL},
    // {0,0,7046495,0,1165664045LL,0,7928670113LL,0,687963472,0,471LL},
    // {0,0,723252621,0,18774297542LL,0,7561331337LL,0,8354046610LL,0,1041LL},
    // {0,0,729494235,0,95266800720LL,0,21268982733LL,0,17711593048LL,0,186LL},
    // {0,0,743552369,0,15397706324LL,0,8627555433LL,0,10298537042LL,0,471LL},
    // {0,0,774477916,0,19720857975LL,0,73639089091LL,0,30920487355LL,0,319LL},
    // {0,0,7836200,0,8092126770LL,0,35148856190LL,0,662698025,0,471LL},
    // {0,0,786126978,0,11628633016LL,0,11065182702LL,0,12047852299LL,0,357LL},
    // {0,0,78788543,0,5535039510LL,0,8581020189LL,0,3016582611LL,0,1383LL},
    // {0,0,790608,0,436809828,182,7755223763LL,0,125714771,0,1611LL},
    // {0,0,7937930,0,5882386601LL,0,2163169659LL,0,2044644070LL,0,319LL},
    // {0,0,8019522192LL,0,193510080416LL,0,472064344100LL,0,293986961441LL,0,548LL},
    // {0,0,806563695,0,0,0,42214050055LL,0,32556045670LL,0,528LL},
    // {0,0,8166264255LL,0,240,213150,136802051205LL,0,127251647861LL,0,243LL},
    // {0,0,819064965,0,88235799015LL,0,24965732996LL,0,23006008980LL,0,110LL},
    // {0,0,8245999350LL,0,163058712180LL,0,89000492753LL,0,49208430600LL,0,1384LL},
    // {0,0,8453081,0,3758610856LL,0,5320570815LL,0,788792707,0,357LL},
    // {0,0,8,6,0,6,0,8,4,0,2580LL},
    // {0,0,8606104340LL,0,3668907088LL,0,48528107058LL,0,19555171482LL,0,110LL},
    // {0,0,882985819,0,14,35126,19619676469LL,0,15824321373LL,0,243LL},
    // {0,0,88466206,0,17484960675LL,0,60409655002LL,0,4612052025LL,0,129LL},
    // {0,0,89500439,0,1338776712LL,12012,21453250599LL,0,1440018611LL,0,91LL},
    // {0,0,9010286040LL,0,153594395955LL,0,87914709811LL,0,66182228400LL,0,529LL},
    // {0,0,9270006488LL,0,315533727736LL,0,605214503092LL,0,222658246353LL,0,700LL},
    // {0,0,9515217105LL,0,133686382830LL,0,92556458175LL,0,84430715387LL,0,358LL},
    // {0,0,958738395,0,76113947910LL,0,35849678769LL,0,29064132220LL,0,53LL},
    // {0,0,98970769,0,8912425522LL,0,8080926337LL,0,6918626274LL,0,1079LL},
    // {0,1,1,1,1,1,1,1,1,1,1041LL},
    // {0,1,2,6,24,120,720,5040,40320,362880,2067LL},
    // {0,13060694016LL,78364164096LL,470184984576LL,2821109907456LL,16926659444736LL,1,7,49,343,927LL},
    // {0,1,48104723380LL,15,24218431805LL,6638885,342906589613LL,15,142978182070LL,120,928LL},
    // {0,1,574289772576LL,17,2661527233449LL,19952441,9348828582989LL,17,5434361620523LL,153,130LL},
    // {0,2,0,4,0,8,0,5,2,4,3207LL},
    // {0,2,0,4,0,8,0,5,2,4,471LL},
    // {0,2187,6561,19683,59049,177147,531441,1594323,4782969,14348907,1554LL},
    // {0,2,4,8,16,32,64,128,256,512,1212LL},
    // {0,2,6,0,8,0,0,8,0,0,1383LL},
    // {0,2,6,0,8,6,6,8,0,8,4119LL},
    // {0,2,6,5,8,8,0,8,0,4,319LL},
    // {0,2,6,5,8,8,0,8,0,8,3093LL},
    // {0,2,8,4,0,4,8,2,6,0,2067LL},
    // {0,2,8,4,0,6,2,8,8,0,471LL},
    // {0,2,8,8,6,0,4,6,0,0,1383LL},
    // {0,3,4,5,6,7,8,9,0,2,1383LL},
    // {0,4,0,0,6,6,8,2,0,6,623LL},
    // {0,4,0,6,0,6,0,6,8,0,91LL},
    // {0,4,0,9,8,4,8,0,0,8,699LL},
    // {0,4782969,43046721,387420489,3486784401LL,31381059609LL,282429536481LL,2541865828329LL,22876792454961LL,205891132094649LL,1839LL},
    // {0,4,8,2,6,0,8,6,6,8,1212LL},
    // {0,5,0,0,0,5,0,0,0,0,927LL},
    // {0,5,0,0,0,5,0,0,0,6,2580LL},
    // {0,549755813888LL,4398046511104LL,35184372088832LL,281474976710656LL,2251799813685248LL,1,9,81,729,1611LL},
    // {0,5,6,7,8,9,0,1,2,3,1440LL},
    // {0,6,0,0,0,0,0,0,0,0,1041LL},
    // {0,6,0,0,0,0,0,0,0,0,167LL},
    // {0,6,0,0,0,4,6,2,6,0,1383LL},
    // {0,6,0,0,0,6,6,6,8,0,528LL},
    // {0,6,0,0,4,8,0,6,0,0,699LL},
    // {0,6,2,0,6,0,6,0,0,6,2067LL},
    // {0,6,2,8,8,0,8,8,6,0,2751LL},
    // {0,6,36,216,1296,7776,46656,279936,1679616,10077696,699LL},
    // {0,6,6,4,0,6,0,6,2,0,471LL},
    // {0,6,6,4,0,8,6,4,0,0,2751LL},
    // {0,6,6,6,8,0,0,2,6,6,3207LL},
    // {0,6,6,6,8,0,0,2,6,6,471LL},
    // {0,67108864,268435456,1073741824,4294967296LL,17179869184LL,1,5,25,125,243LL},
    // {0,78125,390625,1953125,9765625,48828125,244140625,1220703125LL,6103515625LL,30517578125LL,471LL},
    // {0,8,0,0,0,2,2,0,8,6,167LL},
    // {0,8,0,0,2,6,6,0,0,0,1079LL},
    // {0,8,0,3,6,9,2,5,8,2,2010LL},
    // {0,8,0,5,0,5,0,0,0,5,2409LL},
    // {0,8,0,8,0,8,6,8,6,0,357LL},
    // {0,8,0,8,2,8,8,0,8,0,1611LL},
    // {0,8192,16384,32768,65536,131072,1,3,9,27,1383LL},
    // {0,8,4,0,6,0,2,0,6,8,699LL},
    // {0,8,4,8,0,0,0,0,0,0,414LL},
    // {0,8,4,8,0,8,8,0,4,0,243LL},
    // {0,8,6,2,6,0,0,4,0,6,623LL},
    // {0,8,6,4,0,0,6,6,8,2,1554LL},
    // {0,8,64,512,4096,32768,262144,2097152,16777216,134217728,1383LL},
    // {0,8,6,8,0,0,0,6,0,0,1231LL},
    // {0,8,8,0,8,8,6,0,0,8,1611LL}
};

//LL p1[10][18];
LL p[][18]={
    {1LL,0LL,0LL,0LL,0LL,0LL,0LL,0LL,0LL,0LL,0LL,0LL,0LL,0LL,0LL,0LL,0LL,0LL},
    {1LL,1LL,1LL,1LL,1LL,1LL,1LL,1LL,1LL,1LL,1LL,1LL,1LL,1LL,1LL,1LL,1LL,1LL},
    {1LL,2LL,4LL,8LL,16LL,32LL,64LL,128LL,256LL,512LL,1024LL,2048LL,4096LL,8192LL,16384LL,32768LL,65536LL,131072LL},
    {1LL,3LL,9LL,27LL,81LL,243LL,729LL,2187LL,6561LL,19683LL,59049LL,177147LL,531441LL,1594323LL,4782969LL,14348907LL,43046721LL,129140163LL},
    {1LL,4LL,16LL,64LL,256LL,1024LL,4096LL,16384LL,65536LL,262144LL,1048576LL,4194304LL,16777216LL,67108864LL,268435456LL,1073741824LL,4294967296LL,17179869184LL},
    {1LL,5LL,25LL,125LL,625LL,3125LL,15625LL,78125LL,390625LL,1953125LL,9765625LL,48828125LL,244140625LL,1220703125LL,6103515625LL,30517578125LL,152587890625LL,762939453125LL},
    {1LL,6LL,36LL,216LL,1296LL,7776LL,46656LL,279936LL,1679616LL,10077696LL,60466176LL,362797056LL,2176782336LL,13060694016LL,78364164096LL,470184984576LL,2821109907456LL,16926659444736LL},
    {1LL,7LL,49LL,343LL,2401LL,16807LL,117649LL,823543LL,5764801LL,40353607LL,282475249LL,1977326743LL,13841287201LL,96889010407LL,678223072849LL,4747561509943LL,33232930569601LL,232630513987207LL},
    {1LL,8LL,64LL,512LL,4096LL,32768LL,262144LL,2097152LL,16777216LL,134217728LL,1073741824LL,8589934592LL,68719476736LL,549755813888LL,4398046511104LL,35184372088832LL,281474976710656LL,2251799813685248LL},
    {1LL,9LL,81LL,729LL,6561LL,59049LL,531441LL,4782969LL,43046721LL,387420489LL,3486784401LL,31381059609LL,282429536481LL,2541865828329LL,22876792454961LL,205891132094649LL,1853020188851841LL,16677181699666569LL}
};
LL silnia[]={1,1LL,2LL,6LL,24LL,120LL,720LL,5040LL,40320LL,362880LL,3628800LL,39916800LL,479001600LL,6227020800LL,87178291200LL,1307674368000LL,20922789888000LL,355687428096000LL,6402373705728000LL,121645100408832000LL};

LL liczba_cyfr(LL l) {
    // REP(i,19){
    //     cyfry[i]=0;
    // }
    LL wynik=1;
    while (l>9) {
        cyfry_tmp[wynik-1]=l%10;
        wynik++;
        l=l/10;
    }
    cyfry_tmp[wynik-1]=l;
    FOR(i,0,wynik-1) {
        cyfry[i]=cyfry_tmp[wynik-1-i];
    }
    return wynik;
}

LL mnoz(LL l) {
    LL wynik=1;
    while (l>9) {
        wynik *= l%10;
        l=l/10;
    }
    return wynik*l;
}
unordered_map<LL,int> mapping1;
LL odwzoruj(LL l) {
    unordered_map<LL,int>::iterator it = mapping1.find(l);
    if (it!=mapping1.end()) {
        return it->second;
    }
    if (l <= precomputed) {
        return mapping[l];
    }
    LL l0=l;
    LL wynik=1;
    while (l>9) {
        wynik *= l%10;
        l=l/10;
    }
    wynik*=l;
    wynik = odwzoruj(wynik);
    mapping1[l0]=wynik;
    return wynik;
}

LL odwzoruj1(LL l) {
    if (l <= precomputed) {
        return mapping[l];
    }
    LL wynik=1;
    while (l>9) {
        wynik *= l%10;
        l=l/10;
    }
    wynik*=l;
    return odwzoruj(wynik);
}

void compute2(LL *results, int dlugosc, LL prefix_number=1) {
    if (prefix_number%5==0) {
        FOR(d3, 0, dlugosc){
            int rd3=dlugosc-d3;
            LL l3 = prefix_number*p[3][d3];
            LL wyn3=silnia[dlugosc]/silnia[d3];
            FOR(d7, 0, rd3){
                int rd7=rd3-d7;
                LL l7 = l3*p[7][d7];

                int d9 = rd7;
                LL l9 = l7*p[9][d9];

                LL cyfra = odwzoruj(l9);
                results[cyfra] += wyn3/silnia[d7]/silnia[d9];
            }
        }
    } else {
        FOR(d2, 0, dlugosc){
            int rd2=dlugosc-d2;
            LL l2 = prefix_number*p[2][d2];
            LL wyn2=silnia[dlugosc]/silnia[d2];
            FOR(d3, 0, rd2){
                int rd3=rd2-d3;
                LL l3 = l2*p[3][d3];
                LL wyn3=wyn2/silnia[d3];
                FOR(d4, 0, rd3){
                    int rd4=rd3-d4;
                    LL l4 = l3*p[4][d4];
                    LL wyn4=wyn3/silnia[d4];
                    FOR(d6, 0, rd4){
                        int rd6=rd4-d6;
                        LL l6 = l4*p[6][d6];
                        LL wyn6=wyn4/silnia[d6];
                        FOR(d7, 0, rd6){
                            int rd7=rd6-d7;
                            LL l7 = l6*p[7][d7];
                            LL wyn7=wyn6/silnia[d7];
                            FOR(d8, 0, rd7){
                                int rd8=rd7-d8;
                                LL l8 = l7*p[8][d8];

                                int d9 = rd8;
                                LL l9 = l8*p[9][d9];

                                LL cyfra = odwzoruj(l9);
                                results[cyfra] += wyn7/silnia[d8]/silnia[d9];
                            }
                        }
                    }
                }
            }
        }
    }
}
void compute5(LL *results, int dlugosc, LL prefix_number=1) {
    FOR(d5, 1, dlugosc){
        int rd5=dlugosc-d5;
        LL l5 = prefix_number*p[5][d5];
        LL wyn5=silnia[dlugosc]/silnia[d5];
        FOR(d3, 0, rd5){
            int rd3=rd5-d3;
            LL l3 = l5*p[3][d3];
            LL wyn3=wyn5/silnia[d3];
            FOR(d7, 0, rd3){
                int rd7=rd3-d7;
                LL l7 = l3*p[7][d7];

                int d9 = rd7;
                LL l9 = l7*p[9][d9];

                LL cyfra = odwzoruj(l9);
                results[cyfra] += wyn3/silnia[d7]/silnia[d9];
            }
        }
    }
}
void compute(LL *results, int dlugosc, LL prefix_number=1) {
    compute2(results, dlugosc, prefix_number);
    compute5(results, dlugosc, prefix_number);
}

LL* computeAndMemorizeWitoutOnes(int dlugosc, LL prefix_number=1) {
    LL hash = hash_memorized_result1(dlugosc, prefix_number);
    unordered_map<LL, LL*>::iterator it = memorized_results_map1.find(hash);
    LL *result;
    if (it==memorized_results_map1.end()) {
        result = getNewMemorizedResult();
        memorized_results_map1[hash] = result;

        compute2(result, dlugosc, prefix_number);
        if (prefix_number%2!=0) {
            compute5(result, dlugosc, prefix_number);
        }

    } else {
        result = it->second;
    }
    return result;
}

LL* computeAndMemorize(int dlugosc, LL prefix_number=1) {
    LL hash = hash_memorized_result(dlugosc, prefix_number);
    unordered_map<LL, LL*>::iterator it = memorized_results_map.find(hash);
    LL *result;
    if (it==memorized_results_map.end()) {
        result = getNewMemorizedResult();
        memorized_results_map[hash] = result;

        compute2(result, dlugosc, prefix_number);
        if (prefix_number%2!=0) {
            compute5(result, dlugosc, prefix_number);
        }

        LL mnoznik = 1;
        FOR(d1, 1, dlugosc){
            LL *resultWithOne = computeAndMemorizeWitoutOnes(dlugosc-d1, prefix_number);
            mnoznik *= dlugosc-d1+1;
            FOR(i,1,9) {
                result[i] += resultWithOne[i]*(mnoznik)/silnia[d1];
            }
        }

    } else {
        result = it->second;
    }
    return result;
}
void computeAndAddResult(LL *results, int dlugosc, LL prefix_number=1) {
    LL* result = computeAndMemorize(dlugosc, prefix_number);
    FOR(ri, 1,9) {
        results[ri]+=result[ri];
    }
}

void solve(LL n) {
    FOR(wi, 1, 9) {
        wyniki[wi] = 0;
    }
    int dlugosc = liczba_cyfr(n);
    FOR(di, 1, dlugosc-1) {
        FOR(wi, 1, 9) {
            wyniki[wi] += precomputed_results[di-1][wi-1];
        }
        // compute(wyniki, di, 1);
    }
    // REP(i, dlugosc) {
    //     cout<<cyfry[i]<<" ";
    // }
    // cout<<"\n";

    LL prefix_number=1;
    FOR(dlugosc_prefiksu, 1, dlugosc) {
        int current_digit = cyfry[dlugosc_prefiksu-1];
        FOR(di, 1, current_digit-1) {
            LL newPrefix = prefix_number*di;
            if (newPrefix%10) {
                computeAndAddResult(wyniki, dlugosc-dlugosc_prefiksu, newPrefix);
            }
        }
        prefix_number *= current_digit;
    }

    // int current_digit = cyfry[dlugosc];
    // FOR(di, 1, current_digit-1) {
    //     LL newPrefix = prefix_number*di;
    //     if (newPrefix%10) {
    //         LL cyfra = odwzoruj(newPrefix);
    //         wyniki[cyfra] += 1;
    //     }
    // }

    LL cyfra = odwzoruj(n);
    wyniki[cyfra] += 1;

    // LL ni = 1;
    // wyniki[1]=0;
    // while (n >= ni) {
    //     ni=ni*10+1;
    //     wyniki[1]++;
    // }

    wyniki[0]=n;
    FOR(i, 1, 9) {
        wyniki[0] -= wyniki[i];
    }
    FOR(i, 0, 9) {
        cout<<wyniki[i]<<" ";
    }
    cout<<"\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    FOR(i, 1, 9) {
        mapping[i]=i;
    }
    FOR(i, 10, precomputed) {
        mapping[i]=mapping[mnoz(i)];
    }

    // FOR(newPrefix,1,9999) {
    //     FOR(wi, 0, 9) {
    //         wyniki[wi]=0;
    //     }
    //     int dlugosc;
    //     if (newPrefix < 10) {
    //         dlugosc = 17;
    //     } else if (newPrefix < 100) {
    //         dlugosc = 16;
    //     } else   if (newPrefix < 1000) {
    //         dlugosc = 15;
    //     } else   if (newPrefix < 10000) {
    //         dlugosc = 14;
    //     }
    //     LL hash = hash_memorized_result(dlugosc, mnoz(newPrefix));
    //     memorized_results_map[hash] = to_memorize[newPrefix-1];
    //     if (mnoz(newPrefix) % 10) {
    //         LL *wyn=computeAndMemorize(dlugosc, mnoz(newPrefix));
    //         cout<<"{0,";
    //         FOR(ii, 1, 9) {
    //             cout<<wyn[ii];
    //             if (wyn[ii]>1073741824) {
    //                 cout<<"LL";
    //             }
    //             cout<<",";
    //         }
    //         cout<<hash<<"LL},\n";
    //     }
    // }
    // return 0;
    // REP(i, 260) {
    //     memorized_results_map[to_memorize[i][10]] = to_memorize[i];
    // }
    // FOR(di, 1, 18) {
    //     compute(precomputed_results[di], di, 1);
    //     // cout<<"{";
    //     // FOR(ii, 1, 9){
    //     //     cout<<precomputed_results[di][ii]<<",";
    //     // }
    //     // cout<<"},\n";
    // }

    // FOR(pl, 2, 9) {
    //     p[pl][0] = 1;
    //     p[pl][1] = pl;
    //     FOR(pi, 2, 18) {
    //         p[pl][pi] = pl * p[pl][pi-1];
    //     }
    // }
    int t;
    cin >> t;
    REP(ti, t) {
        LL n;
        cin>>n;

        solve(n);
    }

    return 0;
}