#pragma GCC optimize("Ofast") #pragma GCC target("avx2") #define rd_init() char*rp=({char*mmap();mmap(0l,1l<<25,1,2,0,0ll);}) #define rd() ({int _v=0,_c;while(_c=*rp++-48,_c>=0)_v=_v*10+_c;_v;}) #define rd_long() ({long _v=0,_c;while(_c=*rp++-48,_c>=0)_v=_v*10+_c;_v;}) #define WTHI(v) {unsigned _z=v,_n=0;ulong _d=0;while(++_n,_d=_d<<8|0x30|_z%10,_z/=10);*(ulong*)wp=_d;wp+=_n;} #define WTLO(v) {unsigned _z=v,_n=8;ulong _d=0;while(_d=_d<<8|0x30|_z%10,_z/=10,--_n);*(ulong*)wp=_d;wp+=8;} #define wt(v) if(v>=100000000){WTLO(v/10);*wp++=v%10+'0';}else{WTHI(v);} #define MD 998244353 typedef unsigned long ulong; char wbuf[1<<25]; unsigned const t0[]={ 1, 26, 676, 17576, 456976, 11881376,308915776, 45855352, 193994799, 52643009,370473881,648121729,879255306,899262190,421196821,968673816, 229410391,973448401,353549601,208090449,419129909,914934104,828666585,582199797, 163529427,258787690,739013822,247716665,451167172,749658589,524480607,659319193, 172145017,482793030,573686544,940429202,493294780,846732044, 53657378,396847475, 335590820,739406496,257926189,716614796,663586342,283090891,372652695,704770893, 355644864,262567287,837283344,806235531,997236746,972046571,317102021,258697722, 736674654,186898297,866378310,564460294,700546702,245815898,401747230,462984450, 58663464,527005711,724971897,880870968,941269402,515139980,416462891,845591636, 24006770,624176020,256666872,683872554,810532403,110711065,881998984,970597818, 279434443,277585047,229500751,975797761,414632961,798013456,783462796,405145636, 551343006,359497214,362728387,446738885,634523127,525691654,690806415,990812789, 805023689,965728854,152841379,979142795,501603845, 64523381,679363553,693298377, 57359448,493101295,841701434,921105871,989132527,761336877,828116095,567887057, 789642540,565818980,735872538,166043281,324147894,441890420,508463037,242862373, 324955580,462890256, 56214420,463330567, 67662506,760980803,818858171,327181033, 520752034,562376295,646362728,833521280,708421867,450570188,734137005,120919423, 149171939,883737355, 17551111,456328886,883863153, 20821859,541368334,100155742, 607560586,822909941,432527053,265015495,900936752,464735433,104189022,712425866, 554674162,446107270,618101137, 98719914,570229058,850534566,152522950,970863641, 286345841,457281395,908628387,664717943,312512517,139370618,628903009,379568586, 884584059, 39565415, 30456437,791867362,623664352,243363504,337984986,801654812, 878138052,870213586,664177470,298460219,772255223,113748738,960978482, 29331707, 762624382,861591225,439996084,459210301,958779943,970414046,274656371,153355175, 992501491,848929941,110802700,884381494, 34298725,891766850,226317981,893045741, 259569147,759331704,775981597,210634462,485274247,638198186,621243188,180413240, 697766828,173539174,519041112,517892323,488023809,709686798,483458394,590986008, 391970913,208800208,437583643,396486835,326214180,495613856,907028020,623108401, 228908778,960406463, 14459213,375939538,790228811,581062026,133947381,487898847, 706437786,398984082,391142602,187264122,875889760,811757994,142576431,712254147, 550209468,330025226,594701052,488562057,723681246,847314042, 68789326,790278123, 582344138,167282293,356362206,281218179,323962183,437061934,382922401,971783249, }; unsigned const t1[]={ 1,310255649, 21292268,708970540, 17714050,879753653,644849645, 85267069, 435724833,318545626,701565486,559737857,186254472,216549379,887664334,634033164, 659011181,972869614,968016948, 37422256, 52437386, 71885890,521454126,577621855, 128074564,803981463, 6611870,832158749,305161923,325609455,982324716, 23245519, 671526670,305242632,787433944,483206862,960244419,868874624,220238072,491599888, 406509201,725479179,584491943,452856780,826105486,256978022,947176566, 86254292, 633466570,503896269,684580427, 34500800,709945971,246396524,546012643,743713281, 307266542,659656532,906860085,122699618,565872129,936232733,492323049,789359763, 544153302,132979377, 93186781,271775600,521601917,214132512,467453896,548790311, 587081854,175555375,890665208,194291762,447906589,996170205, 91810692, 13333409, 934071321,818521471,486959353, 66799238,434900092,737582560,211576521,126155702, 987293930,225776791,592300846,706214826,505643104,285314935,527124153,376791422, 190473980,814183987,792814125,766076380,690523353,198738417,630611506,882229107, 981344269,813418341, 17152810,754780095,555507088,653236328,117814360,996705472, 773474542,105970764,887846433,241813674,778654661,857059584,353059002, 51133051, 49965792,427217159,125420388,436462352,187457091,771851535,409571070,610848711, 379370758,188872711,317989034,181758395,610666017,844684398,377506360,853689083, 239300121,223572659,487448769,198731039,538734613,512239224,997109869,889167684, 777728535,686685683,349014396,222235114,753637047,743520069,764453957,502950429, 377492971,535557455,655008827,122565276,896189333,460436422,462246805,862992215, 817319764,381657186,996798211,176876281,202282582,742445148,913135939,743465185, 745587715,842250880,803255551,607637077,336627832,948184711,867901201, 80422518, 655707863,424042507,136495398, 13390658,997947993,923217190,724255186,960429393, 31194427,662246519,251123532,807227355,479751847,784986203,382900586,342303608, 544421568,555493930,130566203,460815209,955818937,282938891,947166331, 34973670, 324372544,428621326, 63506570,918170758, 67247079, 3509831, 59871739,695288069, 156148461,667032004,240809042,840513566,343270292,195093693,649978735,956281648, 465894047,442020769,452002985,225779611, 52933445,855749406,319126845,326718285, 795208408, 51579156, 66719487,719414504,671561745,660439254,926958000,359819779, 374316250,498813663,100986173,493963475,333982246,364268000,272367590,786500604, 192420501, 85164470,532321546,910029811,104402077,918888720,593852938,927050158, 186917342, 78752596,716446427,462888918,423010342,904743360,227266086,424183426, }; unsigned const t2[]={ 1,944368488,747103536,187140280,368772981,182786253,897364219,211263171, 25615497,786077300, 44720034,112002094,728573209,393273306,492113322,710070803, 685619638,181037678,571925278, 93776363,700649662,491333458,452835393,825669926, 536368711, 1481288,968975171,849767155,187229952,714875221,276047909,654734096, 979577925,660462606,753028138,752703065,144592825,823720420,580596153,607450957, 230453107,313012486,576979344, 26671436,106498182,263398439,372982546,356428657, 980827323,877450479, 73051050,658917433,695403701,250788539,473190954,611929167, 467216733, 14534483,963337113,327262955,952551430,308178920,123652471,677912738, 339353240,795299465, 97013587,719585297,561330887,925669473,150317617,260521750, 57679810,986012998,791268126,954131553, 93171365,816608776,405099753,833988860, 524362035,728301557,619292953,383515927,270649121,581585988,600444648, 59863737, 96946194,961043381,461405853,799935235,722465725, 81889341,628506542,288092281, 450565142,676222010,973866063,385040867,315816627,353649752,203392208,764469092, 391396530,253764839,721346903,596153172,672159088,387562106,487665661,724445389, 391131913,795928351,729606723, 4299683,448973326,969532267, 35596413,578181588, 174319134,546090626,236930207,221032255,520510969,142674362,458761942,312336268, 480750826,645351770,915511305,757555511,632584205,294530908,769462228,753313389, 580150385,981395803,660709672,448768950,269859564,461313404,330457150,274450131, 721269817,974574082,162196268,121083229,258092676,682389226,513631567,721503487, 660735215,876512042, 98183311,991523280,464995925,394871529,408682148,760778617, 608784924,206640887,550381306,583560570,189636075,768634406,818426085,115139061, 679912066,370844985,844510077,936308791,578238030,963290395,725910112,385114874, 112621454,486814540,251940646,545862939,644394798,287203988,173542061,656213304, 210496054,803088149, 5529007, 73196557,556332987,679574753,362049365,894630512, 68703106,884769660,348150898,753044990,240742962,475601461, 59563500, 73530187, 339313155,208568098,780607380, 9529939,298766726, 54024635, 42615004,881403067, 453921802,660444943, 37318871,455049004,871124321,730960342,349247016,587087694, 126455248, 71180884,674335321,746238470,333819506,841006748,769031195,870648095, 942285026,480030728,779451548,975584479,410885659,909297127,786727282,114138844, 11066772,471146413,753700347,218249767,119140020,449078233, 75445045,269116123, 431845097, 81536386,827757320,591343175,185387046,491656472,187984132,154909680, 779976716,335011238,328954822,844578258,166931913,431581162,815401029,257764309, }; unsigned const t3[]={ 1,852127815,737081821,637093082,148579152,785023286,735857345,497444627, 820873187,598597635,161711596,753863840,473379239,330820723,870177108,220050301, 255016623,683624219,917380677,751659788,319248120,487018703,997222412, 99416753, 92407826,395868439,826627739,576569501,634461433,870181655,658891113,659763689, 640755667,695357840,530734902,147524579,346033774, 73723481,708756820,687191030, 243640717, 68958051,464157011,289156217,199814243,259537708,566172240,307542799, 503749204,704647280,515592166,690489812,915251816,626269029,866414704,529980905, 340808120,434112692,962770563,446401701,480750826,206923682,659775328, 503044, 678702777,698062216,501055311,301496519,779057549,649523073,633511960,574174895, 539618490,117527901,639534731,393739719, 63692182,236615781,665556427,200296382, 876747195,470355006,953876626,296255346,710829966, 14553391,955499538,955880546, 475292699,458407483,929541247,337827833,527468143,155543970,870394347,183388413, 785530230,559343132,870872103,356509328,378817861,916153894,296273185,553914267, 940784847, 48786078,122371506,135663416,504342988,451944130,648196569,690834867, 2524844,699512491,646650907,675792891,949083594,253151293,598530404, 1, 852127815,737081821,637093082,148579152,785023286,735857345,497444627,820873187, 598597635,161711596,753863840,473379239,330820723,870177108,220050301,255016623, 683624219,917380677,751659788,319248120,487018703,997222412, 99416753, 92407826, 395868439,826627739,576569501,634461433,870181655,658891113,659763689,640755667, 695357840,530734902,147524579,346033774, 73723481,708756820,687191030,243640717, 68958051,464157011,289156217,199814243,259537708,566172240,307542799,503749204, 704647280,515592166,690489812,915251816,626269029,866414704,529980905,340808120, 434112692,962770563,446401701,480750826,206923682,659775328, 503044,678702777, 698062216,501055311,301496519,779057549,649523073,633511960,574174895,539618490, 117527901,639534731,393739719, 63692182,236615781,665556427,200296382,876747195, 470355006,953876626,296255346,710829966, 14553391,955499538,955880546,475292699, 458407483,929541247,337827833,527468143,155543970,870394347,183388413,785530230, 559343132,870872103,356509328,378817861,916153894,296273185,553914267,940784847, 48786078,122371506,135663416,504342988,451944130,648196569,690834867, 2524844, 699512491,646650907,675792891,949083594,253151293,598530404, 1,852127815, 737081821,637093082,148579152,785023286,735857345,497444627,820873187,598597635, 161711596,753863840,473379239,330820723,870177108,220050301,255016623,683624219, }; unsigned const t4[]={ 1,917380677,346033774,866414704,539618490,929541247,504342988,497444627, 395868439,289156217,206923682,200296382,559343132,675792891,870177108,640755667, 515592166,779057549,955499538,940784847,637093082,487018703,687191030,434112692, 393739719,155543970,690834867,161711596,634461433,566172240,678702777,953876626, 378817861,598530404,683624219,147524579,626269029,574174895,458407483,135663416, 735857345, 92407826,464157011,480750826,665556427,785530230,646650907,330820723, 659763689,704647280,301496519, 14553391,553914267,737081821,319248120,708756820, 340808120,639534731,527468143,648196569,598597635,576569501,259537708, 503044, 470355006,356509328,253151293,255016623,530734902,915251816,633511960,475292699, 122371506,785023286, 99416753, 68958051,446401701,236615781,183388413,699512491, 473379239,658891113,503749204,501055311,710829966,296273185,852127815,751659788, 73723481,529980905,117527901,337827833,451944130,820873187,826627739,199814243, 659775328,876747195,870872103,949083594,220050301,695357840,690489812,649523073, 955880546, 48786078,148579152,997222412,243640717,962770563, 63692182,870394347, 2524844,753863840,870181655,307542799,698062216,296255346,916153894, 1, 917380677,346033774,866414704,539618490,929541247,504342988,497444627,395868439, 289156217,206923682,200296382,559343132,675792891,870177108,640755667,515592166, 779057549,955499538,940784847,637093082,487018703,687191030,434112692,393739719, 155543970,690834867,161711596,634461433,566172240,678702777,953876626,378817861, 598530404,683624219,147524579,626269029,574174895,458407483,135663416,735857345, 92407826,464157011,480750826,665556427,785530230,646650907,330820723,659763689, 704647280,301496519, 14553391,553914267,737081821,319248120,708756820,340808120, 639534731,527468143,648196569,598597635,576569501,259537708, 503044,470355006, 356509328,253151293,255016623,530734902,915251816,633511960,475292699,122371506, 785023286, 99416753, 68958051,446401701,236615781,183388413,699512491,473379239, 658891113,503749204,501055311,710829966,296273185,852127815,751659788, 73723481, 529980905,117527901,337827833,451944130,820873187,826627739,199814243,659775328, 876747195,870872103,949083594,220050301,695357840,690489812,649523073,955880546, 48786078,148579152,997222412,243640717,962770563, 63692182,870394347, 2524844, 753863840,870181655,307542799,698062216,296255346,916153894, 1,917380677, 346033774,866414704,539618490,929541247,504342988,497444627,395868439,289156217, 206923682,200296382,559343132,675792891,870177108,640755667,515592166,779057549, }; unsigned const t5[]={ 1,955499538,626269029,319248120,122371506,117527901,243640717,497444627, 155543970,480750826,576569501,699512491,876747195,307542799,870177108,378817861, 301496519,530734902,852127815,955880546,866414704,487018703,135663416,639534731, 68958051,820873187,870394347,206923682,634461433,646650907,470355006,503749204, 220050301,916153894,779057549,147524579,737081821,475292699,529980905,997222412, 504342988,393739719,464157011,598597635,183388413,659775328,870181655,675792891, 953876626,704647280,255016623,296273185,649523073,346033774,637093082,458407483, 340808120, 99416753,451944130, 63692182,289156217,161711596,785530230, 503044, 658891113,949083594,296255346,515592166,683624219,553914267,633511960, 73723481, 148579152,929541247,434112692, 92407826,648196569,236615781,199814243,753863840, 559343132,678702777,659763689,253151293,710829966,690489812,917380677,940784847, 574174895,708756820,785023286,337827833,962770563,395868439,690834867,665556427, 259537708,473379239,870872103,698062216,640755667,598530404, 14553391,915251816, 751659788, 48786078,539618490,687191030,735857345,527468143,446401701,826627739, 2524844,200296382,566172240,330820723,356509328,501055311,695357840, 1, 955499538,626269029,319248120,122371506,117527901,243640717,497444627,155543970, 480750826,576569501,699512491,876747195,307542799,870177108,378817861,301496519, 530734902,852127815,955880546,866414704,487018703,135663416,639534731, 68958051, 820873187,870394347,206923682,634461433,646650907,470355006,503749204,220050301, 916153894,779057549,147524579,737081821,475292699,529980905,997222412,504342988, 393739719,464157011,598597635,183388413,659775328,870181655,675792891,953876626, 704647280,255016623,296273185,649523073,346033774,637093082,458407483,340808120, 99416753,451944130, 63692182,289156217,161711596,785530230, 503044,658891113, 949083594,296255346,515592166,683624219,553914267,633511960, 73723481,148579152, 929541247,434112692, 92407826,648196569,236615781,199814243,753863840,559343132, 678702777,659763689,253151293,710829966,690489812,917380677,940784847,574174895, 708756820,785023286,337827833,962770563,395868439,690834867,665556427,259537708, 473379239,870872103,698062216,640755667,598530404, 14553391,915251816,751659788, 48786078,539618490,687191030,735857345,527468143,446401701,826627739, 2524844, 200296382,566172240,330820723,356509328,501055311,695357840, 1,955499538, 626269029,319248120,122371506,117527901,243640717,497444627,155543970,480750826, 576569501,699512491,876747195,307542799,870177108,378817861,301496519,530734902, }; unsigned const t6[]={ 1,852127815,737081821,637093082,148579152,785023286,735857345,497444627, 820873187,598597635,161711596,753863840,473379239,330820723,870177108,220050301, 255016623,683624219,917380677,751659788,319248120,487018703,997222412, 99416753, 92407826,395868439,826627739,576569501,634461433,870181655,658891113,659763689, 640755667,695357840,530734902,147524579,346033774, 73723481,708756820,687191030, 243640717, 68958051,464157011,289156217,199814243,259537708,566172240,307542799, 503749204,704647280,515592166,690489812,915251816,626269029,866414704,529980905, 340808120,434112692,962770563,446401701,480750826,206923682,659775328, 503044, 678702777,698062216,501055311,301496519,779057549,649523073,633511960,574174895, 539618490,117527901,639534731,393739719, 63692182,236615781,665556427,200296382, 876747195,470355006,953876626,296255346,710829966, 14553391,955499538,955880546, 475292699,458407483,929541247,337827833,527468143,155543970,870394347,183388413, 785530230,559343132,870872103,356509328,378817861,916153894,296273185,553914267, 940784847, 48786078,122371506,135663416,504342988,451944130,648196569,690834867, 2524844,699512491,646650907,675792891,949083594,253151293,598530404, 1, 852127815,737081821,637093082,148579152,785023286,735857345,497444627,820873187, 598597635,161711596,753863840,473379239,330820723,870177108,220050301,255016623, 683624219,917380677,751659788,319248120,487018703,997222412, 99416753, 92407826, 395868439,826627739,576569501,634461433,870181655,658891113,659763689,640755667, 695357840,530734902,147524579,346033774, 73723481,708756820,687191030,243640717, 68958051,464157011,289156217,199814243,259537708,566172240,307542799,503749204, 704647280,515592166,690489812,915251816,626269029,866414704,529980905,340808120, 434112692,962770563,446401701,480750826,206923682,659775328, 503044,678702777, 698062216,501055311,301496519,779057549,649523073,633511960,574174895,539618490, 117527901,639534731,393739719, 63692182,236615781,665556427,200296382,876747195, 470355006,953876626,296255346,710829966, 14553391,955499538,955880546,475292699, 458407483,929541247,337827833,527468143,155543970,870394347,183388413,785530230, 559343132,870872103,356509328,378817861,916153894,296273185,553914267,940784847, 48786078,122371506,135663416,504342988,451944130,648196569,690834867, 2524844, 699512491,646650907,675792891,949083594,253151293,598530404, 1,852127815, 737081821,637093082,148579152,785023286,735857345,497444627,820873187,598597635, 161711596,753863840,473379239,330820723,870177108,220050301,255016623,683624219, }; unsigned const t7[]={ 1,917380677,346033774,866414704,539618490,929541247,504342988,497444627, 395868439,289156217,206923682,200296382,559343132,675792891,870177108,640755667, 515592166,779057549,955499538,940784847,637093082,487018703,687191030,434112692, 393739719,155543970,690834867,161711596,634461433,566172240,678702777,953876626, 378817861,598530404,683624219,147524579,626269029,574174895,458407483,135663416, 735857345, 92407826,464157011,480750826,665556427,785530230,646650907,330820723, 659763689,704647280,301496519, 14553391,553914267,737081821,319248120,708756820, 340808120,639534731,527468143,648196569,598597635,576569501,259537708, 503044, 470355006,356509328,253151293,255016623,530734902,915251816,633511960,475292699, 122371506,785023286, 99416753, 68958051,446401701,236615781,183388413,699512491, 473379239,658891113,503749204,501055311,710829966,296273185,852127815,751659788, 73723481,529980905,117527901,337827833,451944130,820873187,826627739,199814243, 659775328,876747195,870872103,949083594,220050301,695357840,690489812,649523073, 955880546, 48786078,148579152,997222412,243640717,962770563, 63692182,870394347, 2524844,753863840,870181655,307542799,698062216,296255346,916153894, 1, 917380677,346033774,866414704,539618490,929541247,504342988,497444627,395868439, 289156217,206923682,200296382,559343132,675792891,870177108,640755667,515592166, 779057549,955499538,940784847,637093082,487018703,687191030,434112692,393739719, 155543970,690834867,161711596,634461433,566172240,678702777,953876626,378817861, 598530404,683624219,147524579,626269029,574174895,458407483,135663416,735857345, 92407826,464157011,480750826,665556427,785530230,646650907,330820723,659763689, 704647280,301496519, 14553391,553914267,737081821,319248120,708756820,340808120, 639534731,527468143,648196569,598597635,576569501,259537708, 503044,470355006, 356509328,253151293,255016623,530734902,915251816,633511960,475292699,122371506, 785023286, 99416753, 68958051,446401701,236615781,183388413,699512491,473379239, 658891113,503749204,501055311,710829966,296273185,852127815,751659788, 73723481, 529980905,117527901,337827833,451944130,820873187,826627739,199814243,659775328, 876747195,870872103,949083594,220050301,695357840,690489812,649523073,955880546, 48786078,148579152,997222412,243640717,962770563, 63692182,870394347, 2524844, 753863840,870181655,307542799,698062216,296255346,916153894, 1,917380677, 346033774,866414704,539618490,929541247,504342988,497444627,395868439,289156217, 206923682,200296382,559343132,675792891,870177108,640755667,515592166,779057549, }; int main(){ char*wp=wbuf; rd_init(); int t=rd(); while(t--){ ulong l=rd_long(); ulong x=319438194; x=x*t0[l&255]%MD; l>>=8; x=x*t1[l&255]%MD; l>>=8; x=x*t2[l&255]%MD; l>>=8; x=x*t3[l&255]%MD; l>>=8; x=x*t4[l&255]%MD; l>>=8; x=x*t5[l&255]%MD; l>>=8; x=x*t6[l&255]%MD; l>>=8; x=(x*t7[l&255]+(MD-319438194))%MD; wt(x); *wp++='\n'; } write(1,wbuf,wp-wbuf); _exit(0); }