20分求调

#include <iostream> 
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <iomanip>
#include <map> 
#include <queue> 
#include <set>
#include <stack>
#define ll long long
using namespace std;
ll A[1000000] = {0,9,36,81,144,225,324,441,576,729,900,1089,1296,1521,1764,2025,2304,2601,2916,3249,3600,3969,4356,4761,5184,5625,6084,6561,7056,7569,8100,8649,9216,9801,10404,11025,11664,12321,12996,13689,14400,15129,15876,16641,17424,18225,19044,19881,20736,21609,22500,23409,24336,25281,26244,27225,28224,29241,30276,31329,32400,33489,34596,35721,36864,38025,39204,40401,41616,42849,44100,45369,46656,47961,49284,50625,51984,53361,54756,56169,57600,59049,60516,62001,63504,65025,66564,68121,69696,71289,72900,74529,76176,77841,79524,81225,82944,84681,86436,88209,90000,91809,93636,95481,97344,99225,101124,103041,104976,106929,108900,110889,112896,114921,116964,119025,121104,123201,125316,127449,129600,131769,133956,136161,138384,140625,142884,145161,147456,149769,152100,154449,156816,159201,161604,164025,166464,168921,171396,173889,176400,178929,181476,184041,186624,189225,191844,194481,197136,199809,202500,205209,207936,210681,213444,216225,219024,221841,224676,227529,230400,233289,236196,239121,242064,245025,248004,251001,254016,257049,260100,263169,266256,269361,272484,275625,278784,281961,285156,288369,291600,294849,298116,301401,304704,308025,311364,314721,318096,321489,324900,328329,331776,335241,338724,342225,345744,349281,352836,356409,360000,363609,367236,370881,374544,378225,381924,385641,389376,393129,396900,400689,404496,408321,412164,416025,419904,423801,427716,431649,435600,439569,443556,447561,451584,455625,459684,463761,467856,471969,476100,480249,484416,488601,492804,497025,501264,505521,509796,514089,518400,522729,527076,531441,535824,540225,544644,549081,553536,558009,562500,567009,571536,576081,580644,585225,589824,594441,599076,603729,608400,613089,617796,622521,627264,632025,636804,641601,646416,651249,656100,660969,665856,670761,675684,680625,685584,690561,695556,700569,705600,710649,715716,720801,725904,731025,736164,741321,746496,751689,756900,762129,767376,772641,777924,783225,788544,793881,799236,804609,810000,815409,820836,826281,831744,837225,842724,848241,853776,859329,864900,870489,876096,881721,887364,893025,898704,904401,910116,915849,921600,927369,933156,938961,944784,950625,956484,962361,968256,974169,980100,986049,992016,998001,1004004,1010025,1016064,1022121,1028196,1034289,1040400,1046529,1052676,1058841,1065024,1071225,1077444,1083681,1089936,1096209,1102500,1108809,1115136,1121481,1127844,1134225,1140624,1147041,1153476,1159929,1166400,1172889,1179396,1185921,1192464,1199025,1205604,1212201,1218816,1225449,1232100,1238769,1245456,1252161,1258884,1265625,1272384,1279161,1285956,1292769,1299600,1306449,1313316,1320201,1327104,1334025,1340964,1347921,1354896,1361889,1368900,1375929,1382976,1390041,1397124,1404225,1411344,1418481,1425636,1432809,1440000,1447209,1454436,1461681,1468944,1476225,1483524,1490841,1498176,1505529,1512900,1520289,1527696,1535121,1542564,1550025,1557504,1565001,1572516,1580049,1587600,1595169,1602756,1610361,1617984,1625625,1633284,1640961,1648656,1656369,1664100,1671849,1679616,1687401,1695204,1703025,1710864,1718721,1726596,1734489,1742400,1750329,1758276,1766241,1774224,1782225,1790244,1798281,1806336,1814409,1822500,1830609,1838736,1846881,1855044,1863225,1871424,1879641,1887876,1896129,1904400,1912689,1920996,1929321,1937664,1946025,1954404,1962801,1971216,1979649,1988100,1996569,2005056,2013561,2022084,2030625,2039184,2047761,2056356,2064969,2073600,2082249,2090916,2099601,2108304,2117025,2125764,2134521,2143296,2152089,2160900,2169729,2178576,2187441,2196324,2205225,2214144,2223081,2232036,2241009,2250000,2259009,2268036,2277081,2286144,2295225,2304324,2313441,2322576,2331729,2340900,2350089,2359296,2368521,2377764,2387025,2396304,2405601,2414916,2424249,2433600,2442969,2452356,2461761,2471184,2480625,2490084,2499561,2509056,2518569,2528100,2537649,2547216,2556801,2566404,2576025,2585664,2595321,2604996,2614689,2624400,2634129,2643876,2653641,2663424,2673225,2683044,2692881,2702736,2712609,2722500,2732409,2742336,2752281,2762244,2772225,2782224,2792241,2802276,2812329,2822400,2832489,2842596,2852721,2862864,2873025,2883204,2893401,2903616,2913849,2924100,2934369,2944656,2954961,2965284,2975625,2985984,2996361,3006756,3017169,3027600,3038049,3048516,3059001,3069504,3080025,3090564,3101121,3111696,3122289,3132900,3143529,3154176,3164841,3175524,3186225,3196944,3207681,3218436,3229209,3240000,3250809,3261636,3272481,3283344,3294225,3305124,3316041,3326976,3337929,3348900,3359889,3370896,3381921,3392964,3404025,3415104,3426201,3437316,3448449,3459600,3470769,3481956,3493161,3504384,3515625,3526884,3538161,3549456,3560769,3572100,3583449,3594816,3606201,3617604,3629025,3640464,3651921,3663396,3674889,3686400,3697929,3709476,3721041,3732624,3744225,3755844,3767481,3779136,3790809,3802500,3814209,3825936,3837681,3849444,3861225,3873024,3884841,3896676,3908529,3920400,3932289,3944196,3956121,3968064,3980025,3992004,4004001,4016016,4028049,4040100,4052169,4064256,4076361,4088484,4100625,4112784,4124961,4137156,4149369,4161600,4173849,4186116,4198401,4210704,4223025,4235364,4247721,4260096,4272489,4284900,4297329,4309776,4322241,4334724,4347225,4359744,4372281,4384836,4397409,4410000,4422609,4435236,4447881,4460544,4473225,4485924,4498641,4511376,4524129,4536900,4549689,4562496,4575321,4588164,4601025,4613904,4626801,4639716,4652649,4665600,4678569,4691556,4704561,4717584,4730625,4743684,4756761,4769856,4782969,4796100,4809249,4822416,4835601,4848804,4862025,4875264,4888521,4901796,4915089,4928400,4941729,4955076,4968441,4981824,4995225,5008644,5022081,5035536,5049009,5062500,5076009,5089536,5103081,5116644,5130225,5143824,5157441,5171076,5184729,5198400,5212089,5225796,5239521,5253264,5267025,5280804,5294601,5308416,5322249,5336100,5349969,5363856,5377761,5391684,5405625,5419584,5433561,5447556,5461569,5475600,5489649,5503716,5517801,5531904,5546025,5560164,5574321,5588496,5602689,5616900,5631129,5645376,5659641,5673924,5688225,5702544,5716881,5731236,5745609,5760000,5774409,5788836,5803281,5817744,5832225,5846724,5861241,5875776,5890329,5904900,5919489,5934096,5948721,5963364,5978025,5992704,6007401,6022116,6036849,6051600,6066369,6081156,6095961,6110784,6125625,6140484,6155361,6170256,6185169,6200100,6215049,6230016,6245001,6260004,6275025,6290064,6305121,6320196,6335289,6350400,6365529,6380676,6395841,6411024,6426225,6441444,6456681,6471936,6487209,6502500,6517809,6533136,6548481,6563844,6579225,6594624,6610041,6625476,6640929,6656400,6671889,6687396,6702921,6718464,6734025,6749604,6765201,6780816,6796449,6812100,6827769,6843456,6859161,6874884,6890625,6906384,6922161,6937956,6953769,6969600,6985449,7001316,7017201,7033104,7049025,7064964,7080921,7096896,7112889,7128900,7144929,7160976,7177041,7193124,7209225,7225344,7241481,7257636,7273809,7290000,7306209,7322436,7338681,7354944,7371225,7387524,7403841,7420176,7436529,7452900,7469289,7485696,7502121,7518564,7535025,7551504,7568001,7584516,7601049,7617600,7634169,7650756,7667361,7683984,7700625,7717284,7733961,7750656,7767369,7784100,7800849,7817616,7834401,7851204,7868025,7884864,7901721,7918596,7935489,7952400,7969329,7986276,8003241,8020224,8037225,8054244,8071281,8088336,8105409,8122500,8139609,8156736,8173881,8191044,8208225,8225424,8242641,8259876,8277129,8294400,8311689,8328996,8346321,8363664,8381025,8398404,8415801,8433216,8450649,8468100,8485569,8503056,8520561,8538084,8555625,8573184,8590761,8608356,8625969,8643600,8661249,8678916,8696601,8714304,8732025,8749764,8767521,8785296,8803089,8820900,8838729,8856576,8874441,8892324,8910225,8928144,8946081,8964036,8982009,9000000,9018009,9036036,9054081,9072144,9090225,9108324,9126441,9144576,9162729,9180900,9199089,9217296,9235521,9253764,9272025,9290304,9308601,9326916,9345249,9363600,9381969,9400356,9418761,9437184,9455625,9474084,9492561,9511056,9529569,9548100,9566649,9585216,9603801,9622404,9641025,9659664,9678321,9696996,9715689,9734400,9753129,9771876,9790641,9809424,9828225,9847044,9865881,9884736,9903609,9922500,9941409,9960336,9979281,9998244,10017225,10036224,10055241,10074276,10093329,10112400,10131489,10150596,10169721,10188864,10208025,10227204,10246401,10265616,10284849,10304100,10323369,10342656,10361961,10381284,10400625,10419984,10439361,10458756,10478169,10497600,10517049,10536516,10556001,10575504,10595025,10614564,10634121,10653696,10673289,10692900,10712529,10732176,10751841,10771524,10791225,10810944,10830681,10850436,10870209,10890000,10909809,10929636,10949481,10969344,10989225,11009124,11029041,11048976,11068929,11088900,11108889,11128896,11148921,11168964,11189025,11209104,11229201,11249316,11269449,11289600,11309769,11329956,11350161,11370384,11390625,11410884,11431161,11451456,11471769,11492100,11512449,11532816,11553201,11573604,11594025,11614464,11634921,11655396,11675889,11696400,11716929,11737476,11758041,11778624,11799225,11819844,11840481,11861136,11881809,11902500,11923209,11943936,11964681,11985444,12006225,12027024,12047841,12068676,12089529,12110400,12131289,12152196,12173121,12194064,12215025,12236004,12257001,12278016,12299049,12320100,12341169,12362256,12383361,12404484,12425625,12446784,12467961,12489156,12510369,12531600,12552849,12574116,12595401,12616704,12638025,12659364,12680721,12702096,12723489,12744900,12766329,12787776,12809241,12830724,12852225,12873744,12895281,12916836,12938409,12960000,12981609,13003236,13024881,13046544,13068225,13089924,13111641,13133376,13155129,13176900,13198689,13220496,13242321,13264164,13286025,13307904,13329801,13351716,13373649,13395600,13417569,13439556,13461561,13483584,13505625,13527684,13549761,13571856,13593969,13616100,13638249,13660416,13682601,13704804,13727025,13749264,13771521,13793796,13816089,13838400,13860729,13883076,13905441,13927824,13950225,13972644,13995081,14017536,14040009,14062500,14085009,14107536,14130081,14152644,14175225,14197824,14220441,14243076,14265729,14288400,14311089,14333796,14356521,14379264,14402025,14424804,14447601,14470416,14493249,14516100,14538969,14561856,14584761,14607684,14630625,14653584,14676561,14699556,14722569,14745600,14768649,14791716,14814801,14837904,14861025,14884164,14907321,14930496,14953689,14976900,15000129,15023376,15046641,15069924,15093225,15116544,15139881,15163236,15186609,15210000,15233409,15256836,15280281,15303744,15327225,15350724,15374241,15397776,15421329,15444900,15468489,15492096,15515721,15539364,15563025,15586704,15610401,15634116,15657849,15681600,15705369,15729156,15752961,15776784,15800625,15824484,15848361,15872256,15896169,15920100,15944049,15968016,15992001,16016004,16040025,16064064,16088121,16112196,16136289,16160400,16184529,16208676,16232841,16257024,16281225,16305444,16329681,16353936,16378209,16402500,16426809,16451136,16475481,16499844,16524225,16548624,16573041,16597476,16621929,16646400,16670889,16695396,16719921,16744464,16769025,16793604,16818201,16842816,16867449,16892100,16916769,16941456,16966161,16990884,17015625,17040384,17065161,17089956,17114769,17139600,17164449,17189316,17214201,17239104,17264025,17288964,17313921,17338896,17363889,17388900,17413929,17438976,17464041,17489124,17514225,17539344,17564481,17589636,17614809,17640000,17665209,17690436,17715681,17740944,17766225,17791524,17816841,17842176,17867529,17892900,17918289,17943696,17969121,17994564,18020025,18045504,18071001,18096516,18122049,18147600,18173169,18198756,18224361,18249984,18275625,18301284,18326961,18352656,18378369,18404100,18429849,18455616,18481401,18507204,18533025,18558864,18584721,18610596,18636489,18662400,18688329,18714276,18740241,18766224,18792225,18818244,18844281,18870336,18896409,18922500,18948609,18974736,19000881,19027044,19053225,19079424,19105641,19131876,19158129,19184400,19210689,19236996,19263321,19289664,19316025,19342404,19368801,19395216,19421649,19448100,19474569,19501056,19527561,19554084,19580625,19607184,19633761,19660356,19686969,19713600,19740249,19766916,19793601,19820304,19847025,19873764,19900521,19927296,19954089,19980900,20007729,20034576,20061441,20088324,20115225,20142144,20169081,20196036,20223009,20250000,20277009,20304036,20331081,20358144,20385225,20412324,20439441,20466576,20493729,20520900,20548089,20575296,20602521,20629764,20657025,20684304,20711601,20738916,20766249,20793600,20820969,20848356,20875761,20903184,20930625,20958084,20985561,21013056,21040569,21068100,21095649,21123216,21150801,21178404,21206025,21233664,21261321,21288996,21316689,21344400,21372129,21399876,21427641,21455424,21483225,21511044,21538881,21566736,21594609,21622500,21650409,21678336,21706281,21734244,21762225,21790224,21818241,21846276,21874329,21902400,21930489,21958596,21986721,22014864,22043025,22071204,22099401,22127616,22155849,22184100,22212369,22240656,22268961,22297284,22325625,22353984,22382361,22410756,22439169,22467600,22496049,22524516,22553001,22581504,22610025,22638564,22667121,22695696,22724289,22752900,22781529,22810176,22838841,22867524,22896225,22924944,22953681,22982436,23011209,23040000,23068809,23097636,23126481,23155344,23184225,23213124,23242041,23270976,23299929,23328900,23357889,23386896,23415921,23444964,23474025,23503104,23532201,23561316,23590449,23619600,23648769,23677956,23707161,23736384,23765625,23794884,23824161,23853456,23882769,23912100,23941449,23970816,24000201,24029604,24059025,24088464,24117921,24147396,24176889,24206400,24235929,24265476,24295041,24324624,24354225,24383844,24413481,24443136,24472809,24502500,24532209,24561936,24591681,24621444,24651225,24681024,24710841,24740676,24770529,24800400,24830289,24860196,24890121,24920064,24950025,24980004,25010001,25040016,25070049,25100100,25130169,25160256,25190361,25220484,25250625,25280784,25310961,25341156,25371369,25401600,25431849,25462116,25492401,25522704,25553025,25583364,25613721,25644096,25674489,25704900,25735329,25765776,25796241,25826724,25857225,25887744,25918281,25948836,25979409,26010000,26040609,26071236,26101881,26132544,26163225,26193924,26224641,26255376,26286129,26316900,26347689,26378496,26409321,26440164,26471025,26501904,26532801,26563716,26594649,26625600,26656569,26687556,26718561,26749584,26780625,26811684,26842761,26873856,26904969,26936100,26967249,26998416,27029601,27060804,27092025,27123264,27154521,27185796,27217089,27248400,27279729,27311076,27342441,27373824,27405225,27436644,27468081,27499536,27531009,27562500,27594009,27625536,27657081,27688644,27720225,27751824,27783441,27815076,27846729,27878400,27910089,27941796,27973521,28005264,28037025,28068804,28100601,28132416,28164249,28196100,28227969,28259856,28291761,28323684,28355625,28387584,28419561,28451556,28483569,28515600,28547649,28579716,28611801,28643904,28676025,28708164,28740321,28772496,28804689,28836900,28869129,28901376,28933641,28965924,28998225,29030544,29062881,29095236,29127609,29160000,29192409,29224836,29257281,29289744,29322225,29354724,29387241,29419776,29452329,29484900,29517489,29550096,29582721,29615364,29648025,29680704,29713401,29746116,29778849,29811600,29844369,29877156,29909961,29942784,29975625,30008484,30041361,30074256,30107169,30140100,30173049,30206016,30239001,30272004,30305025,30338064,30371121,30404196,30437289,30470400,30503529,30536676,30569841,30603024,30636225,30669444,30702681,30735936,30769209,30802500,30835809,30869136,30902481,30935844,30969225,31002624,31036041,31069476,31102929,31136400,31169889,31203396,31236921,31270464,31304025,31337604,31371201,31404816,31438449,31472100,31505769,31539456,31573161,31606884,31640625,31674384,31708161,31741956,31775769,31809600,31843449,31877316,31911201,31945104,31979025,32012964,32046921,32080896,32114889,32148900,32182929,32216976,32251041,32285124,32319225,32353344,32387481,32421636,32455809,32490000,32524209,32558436,32592681,32626944,32661225,32695524,32729841,32764176,32798529,32832900,32867289,32901696,32936121,32970564,33005025,33039504,33074001,33108516,33143049,33177600,33212169,33246756,33281361,33315984,33350625,33385284,33419961,33454656,33489369,33524100,33558849,33593616,33628401,33663204,33698025,33732864,33767721,33802596,33837489,33872400,33907329,33942276,33977241,34012224,34047225,34082244,34117281,34152336,34187409,34222500,34257609,34292736,34327881,34363044,34398225,34433424,34468641,34503876,34539129,34574400,34609689,34644996,34680321,34715664,34751025,34786404,34821801,34857216,34892649,34928100,34963569,34999056,35034561,35070084,35105625,35141184,35176761,35212356,35247969,35283600,35319249,35354916,35390601,35426304,35462025,35497764,35533521,35569296,35605089,35640900,35676729,35712576,35748441,35784324,35820225,35856144,35892081,35928036,35964009,36000000,36036009,36072036,36108081,36144144,36180225,36216324,36252441,36288576,36324729,36360900,36397089,36433296,36469521,36505764,36542025,36578304,36614601,36650916,36687249,36723600,36759969,36796356,36832761,36869184,36905625,36942084,36978561,37015056,37051569,37088100,37124649,37161216,37197801,37234404,37271025,37307664,37344321,37380996,37417689,37454400,37491129,37527876,37564641,37601424,37638225,37675044,37711881,37748736,37785609,37822500,37859409,37896336,37933281,37970244,38007225,38044224,38081241,38118276,38155329,38192400,38229489,38266596,38303721,38340864,38378025,38415204,38452401,38489616,38526849,38564100,38601369,38638656,38675961,38713284,38750625,38787984,38825361,38862756,38900169,38937600,38975049,39012516,39050001,39087504,39125025,39162564,39200121,39237696,39275289,39312900,39350529,39388176,39425841,39463524,39501225,39538944,39576681,39614436,39652209,39690000,39727809,39765636,39803481,39841344,39879225,39917124,39955041,39992976,40030929,40068900,40106889,40144896,40182921,40220964,40259025,40297104,40335201,40373316,40411449,40449600,40487769,40525956,40564161,40602384,40640625,40678884,40717161,40755456,40793769,40832100,40870449,40908816,40947201,40985604,41024025,41062464,41100921,41139396,41177889,41216400,41254929,41293476,41332041,41370624,41409225,41447844,41486481,41525136,41563809,41602500,41641209,41679936,41718681,41757444,41796225,41835024,41873841,41912676,41951529,41990400,42029289,42068196,42107121,42146064,42185025,42224004,42263001,42302016,42341049,42380100,42419169,42458256,42497361,42536484,42575625,42614784,42653961,42693156,42732369,42771600,42810849,42850116,42889401,42928704,42968025,43007364,43046721,43086096,43125489,43164900,43204329,43243776,43283241,43322724,43362225,43401744,43441281,43480836,43520409,43560000,43599609,43639236,43678881,43718544,43758225,43797924,43837641,43877376,43917129,43956900,43996689,44036496,44076321,44116164,44156025,44195904,44235801,44275716,44315649,44355600,44395569,44435556,44475561,44515584,44555625,44595684,44635761,44675856,44715969,44756100,44796249,44836416,44876601,44916804,44957025,44997264,45037521,45077796,45118089,45158400,45198729,45239076,45279441,45319824,45360225,45400644,45441081,45481536,45522009,45562500,45603009,45643536,45684081,45724644,45765225,45805824,45846441,45887076,45927729,45968400,46009089,46049796,46090521,46131264,46172025,46212804,46253601,46294416,46335249,46376100,46416969,46457856,46498761,46539684,46580625,46621584,46662561,46703556,46744569,46785600,46826649,46867716,46908801,46949904,46991025,47032164,47073321,47114496,47155689,47196900,47238129,47279376,47320641,47361924,47403225,47444544,47485881,47527236,47568609,47610000,47651409,47692836,47734281,47775744,47817225,47858724,47900241,47941776,47983329,48024900,48066489,48108096,48149721,48191364,48233025,48274704,48316401,48358116,48399849,48441600,48483369,48525156,48566961,48608784,48650625,48692484,48734361,48776256,48818169,48860100,48902049,48944016,48986001,49028004,49070025,49112064,49154121,49196196,49238289,49280400,49322529,49364676,49406841,49449024,49491225,49533444,49575681,49617936,49660209,49702500,49744809,49787136,49829481,49871844,49914225,49956624,49999041,50041476,50083929,50126400,50168889,50211396,50253921,50296464,50339025,50381604,50424201,50466816,50509449,50552100,50594769,50637456,50680161,50722884,50765625,50808384,50851161,50893956,50936769,50979600,51022449,51065316,51108201,51151104,51194025,51236964,51279921,51322896,51365889,51408900,51451929,51494976,51538041,51581124,51624225,51667344,51710481,51753636,51796809,51840000,51883209,51926436,51969681,52012944,52056225,52099524,52142841,52186176,52229529,52272900,52316289,52359696,52403121,52446564,52490025,52533504,52577001,52620516,52664049,52707600,52751169,52794756,52838361,52881984,52925625,52969284,53012961,53056656,53100369,53144100,53187849,53231616,53275401,53319204,53363025,53406864,53450721,53494596,53538489,53582400,53626329,53670276,53714241,53758224,53802225,53846244,53890281,53934336,53978409,54022500,54066609,54110736,54154881,54199044,54243225,54287424,54331641,54375876,54420129,54464400,54508689,54552996,54597321,54641664,54686025,54730404,54774801,54819216,54863649,54908100,54952569,54997056,55041561,55086084,55130625,55175184,55219761,55264356,55308969,55353600,55398249,55442916,55487601,55532304,55577025,55621764,55666521,55711296,55756089,55800900,55845729,55890576,55935441,55980324,56025225,56070144,56115081,56160036,56205009,56250000,56295009,56340036,56385081,56430144,56475225,56520324,56565441,56610576,56655729,56700900,56746089,56791296,56836521,56881764,56927025,56972304,57017601,57062916,57108249,57153600,57198969,57244356,57289761,57335184,57380625,57426084,57471561,57517056,57562569,57608100,57653649,57699216,57744801,57790404,57836025,57881664,57927321,57972996,58018689,58064400,58110129,58155876,58201641,58247424,58293225,58339044,58384881,58430736,58476609,58522500,58568409,58614336,58660281,58706244,58752225,58798224,58844241,58890276,58936329,58982400,59028489,59074596,59120721,59166864,59213025,59259204,59305401,59351616,59397849,59444100,59490369,59536656,59582961,59629284,59675625,59721984,59768361,59814756,59861169,59907600,59954049,60000516,60047001,60093504,60140025,60186564,60233121,60279696,60326289,60372900,60419529,60466176,60512841,60559524,60606225,60652944,60699681,60746436,60793209,60840000,60886809,60933636,60980481,61027344,61074225,61121124,61168041,61214976,61261929,61308900,61355889,61402896,61449921,61496964,61544025,61591104,61638201,61685316,61732449,61779600,61826769,61873956,61921161,61968384,62015625,62062884,62110161,62157456,62204769,62252100,62299449,62346816,62394201,62441604,62489025,62536464,62583921,62631396,62678889,62726400,62773929,62821476,62869041,62916624,62964225,63011844,63059481,63107136,63154809,63202500,63250209,63297936,63345681,63393444,63441225,63489024,63536841,63584676,63632529,63680400,63728289,63776196,63824121,63872064,63920025,63968004,64016001,64064016,64112049,64160100,64208169,64256256,64304361,64352484,64400625,64448784,64496961,64545156,64593369,64641600,64689849,64738116,64786401,64834704,64883025,64931364,64979721,65028096,65076489,65124900,65173329,65221776,65270241,65318724,65367225,65415744,65464281,65512836,65561409,65610000,65658609,65707236,65755881,65804544,65853225,65901924,65950641,65999376,66048129,66096900,66145689,66194496,66243321,66292164,66341025,66389904,66438801,66487716,66536649,66585600,66634569,66683556,66732561,66781584,66830625,66879684,66928761,66977856,67026969,67076100,67125249,67174416,67223601,67272804,67322025,67371264,67420521,67469796,67519089,67568400,67617729,67667076,67716441,67765824,67815225,67864644,67914081,67963536,68013009,68062500,68112009,68161536,68211081,68260644,68310225,68359824,68409441,68459076,68508729,68558400,68608089,68657796,68707521,68757264,68807025,68856804,68906601,68956416,69006249,69056100,69105969,69155856,69205761,69255684,69305625,69355584,69405561,69455556,69505569,69555600,69605649,69655716,69705801,69755904,69806025,69856164,69906321,69956496,70006689,70056900,70107129,70157376,70207641,70257924,70308225,70358544,70408881,70459236,70509609,70560000,70610409,70660836,70711281,70761744,70812225,70862724,70913241,70963776,71014329,71064900,71115489,71166096,71216721,71267364,71318025,71368704,71419401,71470116,71520849,71571600,71622369,71673156,71723961,71774784,71825625,71876484,71927361,71978256,72029169,72080100,72131049,72182016,72233001,72284004,72335025,72386064,72437121,72488196,72539289,72590400,72641529,72692676,72743841,72795024,72846225,72897444,72948681,72999936,73051209,73102500,73153809,73205136,73256481,73307844,73359225,73410624,73462041,73513476,73564929,73616400,73667889,73719396,73770921,73822464,73874025,73925604,73977201,74028816,74080449,74132100,74183769,74235456,74287161,74338884,74390625,74442384,74494161,74545956,74597769,74649600,74701449,74753316,74805201,74857104,74909025,74960964,75012921,75064896,75116889,75168900,75220929,75272976,75325041,75377124,75429225,75481344,75533481,75585636,75637809,75690000,75742209,75794436,75846681,75898944,75951225,76003524,76055841,76108176,76160529,76212900,76265289,76317696,76370121,76422564,76475025,76527504,76580001,76632516,76685049,76737600,76790169,76842756,76895361,76947984,77000625,77053284,77105961,77158656,77211369,77264100,77316849,77369616,77422401,77475204,77528025,77580864,77633721,77686596,77739489,77792400,77845329,77898276,77951241,78004224,78057225,78110244,78163281,78216336,78269409,78322500,78375609,78428736,78481881,78535044,78588225,78641424,78694641,78747876,78801129,78854400,78907689,78960996,79014321,79067664,79121025,79174404,79227801,79281216,79334649,79388100,79441569,79495056,79548561,79602084,79655625,79709184,79762761,79816356,79869969,79923600,79977249,80030916,80084601,80138304,80192025,80245764,80299521,80353296,80407089,80460900,80514729,80568576,80622441,80676324,80730225,80784144,80838081,80892036,80946009,81000000,81054009,81108036,81162081,81216144,81270225,81324324,81378441,81432576,81486729,81540900,81595089,81649296,81703521,81757764,81812025,81866304,81920601,81974916,82029249,82083600,82137969,82192356,82246761,82301184,82355625,82410084,82464561,82519056,82573569,82628100,82682649,82737216,82791801,82846404,82901025,82955664,83010321,83064996,83119689,83174400,83229129,83283876,83338641,83393424,83448225,83503044,83557881,83612736,83667609,83722500,83777409,83832336,83887281,83942244,83997225,84052224,84107241,84162276,84217329,84272400,84327489,84382596,84437721,84492864,84548025,84603204,84658401,84713616,84768849,84824100,84879369,84934656,84989961,85045284,85100625,85155984,85211361,85266756,85322169,85377600,85433049,85488516,85544001,85599504,85655025,85710564,85766121,85821696,85877289,85932900,85988529,86044176,86099841,86155524,86211225,86266944,86322681,86378436,86434209,86490000,86545809,86601636,86657481,86713344,86769225,86825124,86881041,86936976,86992929,87048900,87104889,87160896,87216921,87272964,87329025,87385104,87441201,87497316,87553449,87609600,87665769,87721956,87778161,87834384,87890625,87946884,88003161,88059456,88115769,88172100,88228449,88284816,88341201,88397604,88454025,88510464,88566921,88623396,88679889,88736400,88792929,88849476,88906041,88962624,89019225,89075844,89132481,89189136,89245809,89302500,89359209,89415936,89472681,89529444,89586225,89643024,89699841,89756676,89813529,89870400,89927289,89984196,90041121,90098064,90155025,90212004,90269001,90326016,90383049,90440100,90497169,90554256,90611361,90668484,90725625,90782784,90839961,90897156,90954369,91011600,91068849,91126116,91183401,91240704,91298025,91355364,91412721,91470096,91527489,91584900,91642329,91699776,91757241,91814724,91872225,91929744,91987281,92044836,92102409,92160000,92217609,92275236,92332881,92390544,92448225,92505924,92563641,92621376,92679129,92736900,92794689,92852496,92910321,92968164,93026025,93083904,93141801,93199716,93257649,93315600,93373569,93431556,93489561,93547584,93605625,93663684,93721761,93779856,93837969,93896100,93954249,94012416,94070601,94128804,94187025,94245264,94303521,94361796,94420089,94478400,94536729,94595076,94653441,94711824,94770225,94828644,94887081,94945536,95004009,95062500,95121009,95179536,95238081,95296644,95355225,95413824,95472441,95531076,95589729,95648400,95707089,95765796,95824521,95883264,95942025,96000804,96059601,96118416,96177249,96236100,96294969,96353856,96412761,96471684,96530625,96589584,96648561,96707556,96766569,96825600,96884649,96943716,97002801,97061904,97121025,97180164,97239321,97298496,97357689,97416900,97476129,97535376,97594641,97653924,97713225,97772544,97831881,97891236,97950609,98010000,98069409,98128836,98188281,98247744,98307225,98366724,98426241,98485776,98545329,98604900,98664489,98724096,98783721,98843364,98903025,98962704,99022401,99082116,99141849,99201600,99261369,99321156,99380961,99440784,99500625,99560484,99620361,99680256,99740169,99800100,99860049,99920016,99980001};
int main()
{
	ll i,j,t,n,sum = 0;
	cin >> t;
	for(i = 1;i <= t;i++)
	{
		cin >> n;
		sum = 0;
		for(j = 1;j <= n;j++)
		{
			if(A[j] > n)
			{
				break;
			}
			sum++;
		}
		cout << sum << endl;
	}
	return 0;
}