Description
只有质数2,3,5,7这几个作为因子的数叫做,丑数,比如前20个丑数是(从小到大来说) 1,2,3,4,5,6,7,8,9,10,12,14,15,16,18,20,21,24和25.
Input
我们给你个n（1<=m<=5842）当输入n为0结束。
Output
输出第n个丑数。每个数一行。
Accepted Code（打表）
#include <bits/stdc++.h>
using namespace std;
int f[10001];
int num[10001];
//丑数排序思路是选取前有序丑数列中*2 3 5 7任意一个的最小的作为后一个值
/*
void choufilter()
{
num[1] = 1;
for (int i = 2; i < 6000; i++)
{
int bmin = 400000000;
for (int x = 1; x < i; x++)
{
long long a = (long long)num[x] * 2 - num[i - 1];
long long b = (long long)num[x] * 3 - num[i - 1];
long long c = (long long)num[x] * 5 - num[i - 1];
long long d = (long long)num[x] * 7 - num[i - 1];
if (a <= 0)
{
a = 400000000;
}
if (b <= 0)
{
b = 500000000;
}
if (c <= 0)
{
c = 400000000;
}
if (d <= 0)
{
d = 400000000;
}
bmin = min((long long)bmin, min(min(a, b), min(c, d)));
}
num[i] = num[i - 1] + bmin;
}
}
*/
int main()
{
f[1] = 1;
f[2] = 2;
f[3] = 3;
f[4] = 4;
f[5] = 5;
f[6] = 6;
f[7] = 7;
f[8] = 8;
f[9] = 9;
f[10] = 10;
f[11] = 12;
f[12] = 14;
f[13] = 15;
f[14] = 16;
f[15] = 18;
f[16] = 20;
f[17] = 21;
f[18] = 24;
f[19] = 25;
f[20] = 27;
f[21] = 28;
f[22] = 30;
f[23] = 32;
f[24] = 35;
f[25] = 36;
f[26] = 40;
f[27] = 42;
f[28] = 45;
f[29] = 48;
f[30] = 49;
f[31] = 50;
f[32] = 54;
f[33] = 56;
f[34] = 60;
f[35] = 63;
f[36] = 64;
f[37] = 70;
f[38] = 72;
f[39] = 75;
f[40] = 80;
f[41] = 81;
f[42] = 84;
f[43] = 90;
f[44] = 96;
f[45] = 98;
f[46] = 100;
f[47] = 105;
f[48] = 108;
f[49] = 112;
f[50] = 120;
f[51] = 125;
f[52] = 126;
f[53] = 128;
f[54] = 135;
f[55] = 140;
f[56] = 144;
f[57] = 147;
f[58] = 150;
f[59] = 160;
f[60] = 162;
f[61] = 168;
f[62] = 175;
f[63] = 180;
f[64] = 189;
f[65] = 192;
f[66] = 196;
f[67] = 200;
f[68] = 210;
f[69] = 216;
f[70] = 224;
f[71] = 225;
f[72] = 240;
f[73] = 243;
f[74] = 245;
f[75] = 250;
f[76] = 252;
f[77] = 256;
f[78] = 270;
f[79] = 280;
f[80] = 288;
f[81] = 294;
f[82] = 300;
f[83] = 315;
f[84] = 320;
f[85] = 324;
f[86] = 336;
f[87] = 343;
f[88] = 350;
f[89] = 360;
f[90] = 375;
f[91] = 378;
f[92] = 384;
f[93] = 392;
f[94] = 400;
f[95] = 405;
f[96] = 420;
f[97] = 432;
f[98] = 441;
f[99] = 448;
f[100] = 450;
f[101] = 480;
f[102] = 486;
f[103] = 490;
f[104] = 500;
f[105] = 504;
f[106] = 512;
f[107] = 525;
f[108] = 540;
f[109] = 560;
f[110] = 567;
f[111] = 576;
f[112] = 588;
f[113] = 600;
f[114] = 625;
f[115] = 630;
f[116] = 640;
f[117] = 648;
f[118] = 672;
f[119] = 675;
f[120] = 686;
f[121] = 700;
f[122] = 720;
f[123] = 729;
f[124] = 735;
f[125] = 750;
f[126] = 756;
f[127] = 768;
f[128] = 784;
f[129] = 800;
f[130] = 810;
f[131] = 840;
f[132] = 864;
f[133] = 875;
f[134] = 882;
f[135] = 896;
f[136] = 900;
f[137] = 945;
f[138] = 960;
f[139] = 972;
f[140] = 980;
f[141] = 1000;
f[142] = 1008;
f[143] = 1024;
f[144] = 1029;
f[145] = 1050;
f[146] = 1080;
f[147] = 1120;
f[148] = 1125;
f[149] = 1134;
f[150] = 1152;
f[151] = 1176;
f[152] = 1200;
f[153] = 1215;
f[154] = 1225;
f[155] = 1250;
f[156] = 1260;
f[157] = 1280;
f[158] = 1296;
f[159] = 1323;
f[160] = 1344;
f[161] = 1350;
f[162] = 1372;
f[163] = 1400;
f[164] = 1440;
f[165] = 1458;
f[166] = 1470;
f[167] = 1500;
f[168] = 1512;
f[169] = 1536;
f[170] = 1568;
f[171] = 1575;
f[172] = 1600;
f[173] = 1620;
f[174] = 1680;
f[175] = 1701;
f[176] = 1715;
f[177] = 1728;
f[178] = 1750;
f[179] = 1764;
f[180] = 1792;
f[181] = 1800;
f[182] = 1875;
f[183] = 1890;
f[184] = 1920;
f[185] = 1944;
f[186] = 1960;
f[187] = 2000;
f[188] = 2016;
f[189] = 2025;
f[190] = 2048;
f[191] = 2058;
f[192] = 2100;
f[193] = 2160;
f[194] = 2187;
f[195] = 2205;
f[196] = 2240;
f[197] = 2250;
f[198] = 2268;
f[199] = 2304;
f[200] = 2352;
f[201] = 2400;
f[202] = 2401;
f[203] = 2430;
f[204] = 2450;
f[205] = 2500;
f[206] = 2520;
f[207] = 2560;
f[208] = 2592;
f[209] = 2625;
f[210] = 2646;
f[211] = 2688;
f[212] = 2700;
f[213] = 2744;
f[214] = 2800;
f[215] = 2835;
f[216] = 2880;
f[217] = 2916;
f[218] = 2940;
f[219] = 3000;
f[220] = 3024;
f[221] = 3072;
f[222] = 3087;
f[223] = 3125;
f[224] = 3136;
f[225] = 3150;
f[226] = 3200;
f[227] = 3240;
f[228] = 3360;
f[229] = 3375;
f[230] = 3402;
f[231] = 3430;
f[232] = 3456;
f[233] = 3500;
f[234] = 3528;
f[235] = 3584;
f[236] = 3600;
f[237] = 3645;
f[238] = 3675;
f[239] = 3750;
f[240] = 3780;
f[241] = 3840;
f[242] = 3888;
f[243] = 3920;
f[244] = 3969;
f[245] = 4000;
f[246] = 4032;
f[247] = 4050;
f[248] = 4096;
f[249] = 4116;
f[250] = 4200;
f[251] = 4320;
f[252] = 4374;
f[253] = 4375;
f[254] = 4410;
f[255] = 4480;
f[256] = 4500;
f[257] = 4536;
f[258] = 4608;
f[259] = 4704;
f[260] = 4725;
f[261] = 4800;
f[262] = 4802;
f[263] = 4860;
f[264] = 4900;
f[265] = 5000;
f[266] = 5040;
f[267] = 5103;
f[268] = 5120;
f[269] = 5145;
f[270] = 5184;
f[271] = 5250;
f[272] = 5292;
f[273] = 5376;
f[274] = 5400;
f[275] = 5488;
f[276] = 5600;
f[277] = 5625;
f[278] = 5670;
f[279] = 5760;
f[280] = 5832;
f[281] = 5880;
f[282] = 6000;
f[283] = 6048;
f[284] = 6075;
f[285] = 6125;
f[286] = 6144;
f[287] = 6174;
f[288] = 6250;
f[289] = 6272;
f[290] = 6300;
f[291] = 6400;
f[292] = 6480;
f[293] = 6561;
f[294] = 6615;
f[295] = 6720;
f[296] = 6750;
f[297] = 6804;
f[298] = 6860;
f[299] = 6912;
f[300] = 7000;
f[301] = 7056;
f[302] = 7168;
f[303] = 7200;
f[304] = 7203;
f[305] = 7290;
f[306] = 7350;
f[307] = 7500;
f[308] = 7560;
f[309] = 7680;
f[310] = 7776;
f[311] = 7840;
f[312] = 7875;
f[313] = 7938;
f[314] = 8000;
f[315] = 8064;
f[316] = 8100;
f[317] = 8192;
f[318] = 8232;
f[319] = 8400;
f[320] = 8505;
f[321] = 8575;
f[322] = 8640;
f[323] = 8748;
f[324] = 8750;
f[325] = 8820;
f[326] = 8960;
f[327] = 9000;
f[328] = 9072;
f[329] = 9216;
f[330] = 9261;
f[331] = 9375;
f[332] = 9408;
f[333] = 9450;
f[334] = 9600;
f[335] = 9604;
f[336] = 9720;
f[337] = 9800;
f[338] = 10000;
f[339] = 10080;
f[340] = 10125;
f[341] = 10206;
f[342] = 10240;
f[343] = 10290;
f[344] = 10368;
f[345] = 10500;
f[346] = 10584;
f[347] = 10752;
f[348] = 10800;
f[349] = 10935;
f[350] = 10976;
f[351] = 11025;
f[352] = 11200;
f[353] = 11250;
f[354] = 11340;
f[355] = 11520;
f[356] = 11664;
f[357] = 11760;
f[358] = 11907;
f[359] = 12000;
f[360] = 12005;
f[361] = 12096;
f[362] = 12150;
f[363] = 12250;
f[364] = 12288;
f[365] = 12348;
f[366] = 12500;
f[367] = 12544;
f[368] = 12600;
f[369] = 12800;
f[370] = 12960;
f[371] = 13122;
f[372] = 13125;
f[373] = 13230;
f[374] = 13440;
f[375] = 13500;
f[376] = 13608;
f[377] = 13720;
f[378] = 13824;
f[379] = 14000;
f[380] = 14112;
f[381] = 14175;
f[382] = 14336;
f[383] = 14400;
f[384] = 14406;
f[385] = 14580;
f[386] = 14700;
f[387] = 15000;
f[388] = 15120;
f[389] = 15309;
f[390] = 15360;
f[391] = 15435;
f[392] = 15552;
f[393] = 15625;
f[394] = 15680;
f[395] = 15750;
f[396] = 15876;
f[397] = 16000;
f[398] = 16128;
f[399] = 16200;
f[400] = 16384;
f[401] = 16464;
f[402] = 16800;
f[403] = 16807;
f[404] = 16875;
f[405] = 17010;
f[406] = 17150;
f[407] = 17280;
f[408] = 17496;
f[409] = 17500;
f[410] = 17640;
f[411] = 17920;
f[412] = 18000;
f[413] = 18144;
f[414] = 18225;
f[415] = 18375;
f[416] = 18432;
f[417] = 18522;
f[418] = 18750;
f[419] = 18816;
f[420] = 18900;
f[421] = 19200;
f[422] = 19208;
f[423] = 19440;
f[424] = 19600;
f[425] = 19683;
f[426] = 19845;
f[427] = 20000;
f[428] = 20160;
f[429] = 20250;
f[430] = 20412;
f[431] = 20480;
f[432] = 20580;
f[433] = 20736;
f[434] = 21000;
f[435] = 21168;
f[436] = 21504;
f[437] = 21600;
f[438] = 21609;
f[439] = 21870;
f[440] = 21875;
f[441] = 21952;
f[442] = 22050;
f[443] = 22400;
f[444] = 22500;
f[445] = 22680;
f[446] = 23040;
f[447] = 23328;
f[448] = 23520;
f[449] = 23625;
f[450] = 23814;
f[451] = 24000;
f[452] = 24010;
f[453] = 24192;
f[454] = 24300;
f[455] = 24500;
f[456] = 24576;
f[457] = 24696;
f[458] = 25000;
f[459] = 25088;
f[460] = 25200;
f[461] = 25515;
f[462] = 25600;
f[463] = 25725;
f[464] = 25920;
f[465] = 26244;
f[466] = 26250;
f[467] = 26460;
f[468] = 26880;
f[469] = 27000;
f[470] = 27216;
f[471] = 27440;
f[472] = 27648;
f[473] = 27783;
f[474] = 28000;
f[475] = 28125;
f[476] = 28224;
f[477] = 28350;
f[478] = 28672;
f[479] = 28800;
f[480] = 28812;
f[481] = 29160;
f[482] = 29400;
f[483] = 30000;
f[484] = 30240;
f[485] = 30375;
f[486] = 30618;
f[487] = 30625;
f[488] = 30720;
f[489] = 30870;
f[490] = 31104;
f[491] = 31250;
f[492] = 31360;
f[493] = 31500;
f[494] = 31752;
f[495] = 32000;
f[496] = 32256;
f[497] = 32400;
f[498] = 32768;
f[499] = 32805;
f[500] = 32928;
f[501] = 33075;
f[502] = 33600;
f[503] = 33614;
f[504] = 33750;
f[505] = 34020;
f[506] = 34300;
f[507] = 34560;
f[508] = 34992;
f[509] = 35000;
f[510] = 35280;
f[511] = 35721;
f[512] = 35840;
f[513] = 36000;
f[514] = 36015;
f[515] = 36288;
f[516] = 36450;
f[517] = 36750;
f[518] = 36864;
f[519] = 37044;
f[520] = 37500;
f[521] = 37632;
f[522] = 37800;
f[523] = 38400;
f[524] = 38416;
f[525] = 38880;
f[526] = 39200;
f[527] = 39366;
f[528] = 39375;
f[529] = 39690;
f[530] = 40000;
f[531] = 40320;
f[532] = 40500;
f[533] = 40824;
f[534] = 40960;
f[535] = 41160;
f[536] = 41472;
f[537] = 42000;
f[538] = 42336;
f[539] = 42525;
f[540] = 42875;
f[541] = 43008;
f[542] = 43200;
f[543] = 43218;
f[544] = 43740;
f[545] = 43750;
f[546] = 43904;
f[547] = 44100;
f[548] = 44800;
f[549] = 45000;
f[550] = 45360;
f[551] = 45927;
f[552] = 46080;
f[553] = 46305;
f[554] = 46656;
f[555] = 46875;
f[556] = 47040;
f[557] = 47250;
f[558] = 47628;
f[559] = 48000;
f[560] = 48020;
f[561] = 48384;
f[562] = 48600;
f[563] = 49000;
f[564] = 49152;
f[565] = 49392;
f[566] = 50000;
f[567] = 50176;
f[568] = 50400;
f[569] = 50421;
f[570] = 50625;
f[571] = 51030;
f[572] = 51200;
f[573] = 51450;
f[574] = 51840;
f[575] = 52488;
f[576] = 52500;
f[577] = 52920;
f[578] = 53760;
f[579] = 54000;
f[580] = 54432;
f[581] = 54675;
f[582] = 54880;
f[583] = 55125;
f[584] = 55296;
f[585] = 55566;
f[586] = 56000;
f[587] = 56250;
f[588] = 56448;
f[589] = 56700;
f[590] = 57344;
f[591] = 57600;
f[592] = 57624;
f[593] = 58320;
f[594] = 58800;
f[595] = 59049;
f[596] = 59535;
f[597] = 60000;
f[598] = 60025;
f[599] = 60480;
f[600] = 60750;
f[601] = 61236;
f[602] = 61250;
f[603] = 61440;
f[604] = 61740;
f[605] = 62208;
f[606] = 62500;
f[607] = 62720;
f[608] = 63000;
f[609] = 63504;
f[610] = 64000;
f[611] = 64512;
f[612] = 64800;
f[613] = 64827;
f[614] = 65536;
f[615] = 65610;
f[616] = 65625;
f[617] = 65856;
f[618] = 66150;
f[619] = 67200;
f[620] = 67228;
f[621] = 67500;
f[622] = 68040;
f[623] = 68600;
f[624] = 69120;
f[625] = 69984;
f[626] = 70000;
f[627] = 70560;
f[628] = 70875;
f[629] = 71442;
f[630] = 71680;
f[631] = 72000;
f[632] = 72030;
f[633] = 72576;
f[634] = 72900;
f[635] = 73500;
f[636] = 73728;
f[637] = 74088;
f[638] = 75000;
f[639] = 75264;
f[640] = 75600;
f[641] = 76545;
f[642] = 76800;
f[643] = 76832;
f[644] = 77175;
f[645] = 77760;
f[646] = 78125;
f[647] = 78400;
f[648] = 78732;
f[649] = 78750;
f[650] = 79380;
f[651] = 80000;
f[652] = 80640;
f[653] = 81000;
f[654] = 81648;
f[655] = 81920;
f[656] = 82320;
f[657] = 82944;
f[658] = 83349;
f[659] = 84000;
f[660] = 84035;
f[661] = 84375;
f[662] = 84672;
f[663] = 85050;
f[664] = 85750;
f[665] = 86016;
f[666] = 86400;
f[667] = 86436;
f[668] = 87480;
f[669] = 87500;
f[670] = 87808;
f[671] = 88200;
f[672] = 89600;
f[673] = 90000;
f[674] = 90720;
f[675] = 91125;
f[676] = 91854;
f[677] = 91875;
f[678] = 92160;
f[679] = 92610;
f[680] = 93312;
f[681] = 93750;
f[682] = 94080;
f[683] = 94500;
f[684] = 95256;
f[685] = 96000;
f[686] = 96040;
f[687] = 96768;
f[688] = 97200;
f[689] = 98000;
f[690] = 98304;
f[691] = 98415;
f[692] = 98784;
f[693] = 99225;
f[694] = 100000;
f[695] = 100352;
f[696] = 100800;
f[697] = 100842;
f[698] = 101250;
f[699] = 102060;
f[700] = 102400;
f[701] = 102900;
f[702] = 103680;
f[703] = 104976;
f[704] = 105000;
f[705] = 105840;
f[706] = 107163;
f[707] = 107520;
f[708] = 108000;
f[709] = 108045;
f[710] = 108864;
f[711] = 109350;
f[712] = 109375;
f[713] = 109760;
f[714] = 110250;
f[715] = 110592;
f[716] = 111132;
f[717] = 112000;
f[718] = 112500;
f[719] = 112896;
f[720] = 113400;
f[721] = 114688;
f[722] = 115200;
f[723] = 115248;
f[724] = 116640;
f[725] = 117600;
f[726] = 117649;
f[727] = 118098;
f[728] = 118125;
f[729] = 119070;
f[730] = 120000;
f[731] = 120050;
f[732] = 120960;
f[733] = 121500;
f[734] = 122472;
f[735] = 122500;
f[736] = 122880;
f[737] = 123480;
f[738] = 124416;
f[739] = 125000;
f[740] = 125440;
f[741] = 126000;
f[742] = 127008;
f[743] = 127575;
f[744] = 128000;
f[745] = 128625;
f[746] = 129024;
f[747] = 129600;
f[748] = 129654;
f[749] = 131072;
f[750] = 131220;
f[751] = 131250;
f[752] = 131712;
f[753] = 132300;
f[754] = 134400;
f[755] = 134456;
f[756] = 135000;
f[757] = 136080;
f[758] = 137200;
f[759] = 137781;
f[760] = 138240;
f[761] = 138915;
f[762] = 139968;
f[763] = 140000;
f[764] = 140625;
f[765] = 141120;
f[766] = 141750;
f[767] = 142884;
f[768] = 143360;
f[769] = 144000;
f[770] = 144060;
f[771] = 145152;
f[772] = 145800;
f[773] = 147000;
f[774] = 147456;
f[775] = 148176;
f[776] = 150000;
f[777] = 150528;
f[778] = 151200;
f[779] = 151263;
f[780] = 151875;
f[781] = 153090;
f[782] = 153125;
f[783] = 153600;
f[784] = 153664;
f[785] = 154350;
f[786] = 155520;
f[787] = 156250;
f[788] = 156800;
f[789] = 157464;
f[790] = 157500;
f[791] = 158760;
f[792] = 160000;
f[793] = 161280;
f[794] = 162000;
f[795] = 163296;
f[796] = 163840;
f[797] = 164025;
f[798] = 164640;
f[799] = 165375;
f[800] = 165888;
f[801] = 166698;
f[802] = 168000;
f[803] = 168070;
f[804] = 168750;
f[805] = 169344;
f[806] = 170100;
f[807] = 171500;
f[808] = 172032;
f[809] = 172800;
f[810] = 172872;
f[811] = 174960;
f[812] = 175000;
f[813] = 175616;
f[814] = 176400;
f[815] = 177147;
f[816] = 178605;
f[817] = 179200;
f[818] = 180000;
f[819] = 180075;
f[820] = 181440;
f[821] = 182250;
f[822] = 183708;
f[823] = 183750;
f[824] = 184320;
f[825] = 185220;
f[826] = 186624;
f[827] = 187500;
f[828] = 188160;
f[829] = 189000;
f[830] = 190512;
f[831] = 192000;
f[832] = 192080;
f[833] = 193536;
f[834] = 194400;
f[835] = 194481;
f[836] = 196000;
f[837] = 196608;
f[838] = 196830;
f[839] = 196875;
f[840] = 197568;
f[841] = 198450;
f[842] = 200000;
f[843] = 200704;
f[844] = 201600;
f[845] = 201684;
f[846] = 202500;
f[847] = 204120;
f[848] = 204800;
f[849] = 205800;
f[850] = 207360;
f[851] = 209952;
f[852] = 210000;
f[853] = 211680;
f[854] = 212625;
f[855] = 214326;
f[856] = 214375;
f[857] = 215040;
f[858] = 216000;
f[859] = 216090;
f[860] = 217728;
f[861] = 218700;
f[862] = 218750;
f[863] = 219520;
f[864] = 220500;
f[865] = 221184;
f[866] = 222264;
f[867] = 224000;
f[868] = 225000;
f[869] = 225792;
f[870] = 226800;
f[871] = 229376;
f[872] = 229635;
f[873] = 230400;
f[874] = 230496;
f[875] = 231525;
f[876] = 233280;
f[877] = 234375;
f[878] = 235200;
f[879] = 235298;
f[880] = 236196;
f[881] = 236250;
f[882] = 238140;
f[883] = 240000;
f[884] = 240100;
f[885] = 241920;
f[886] = 243000;
f[887] = 244944;
f[888] = 245000;
f[889] = 245760;
f[890] = 246960;
f[891] = 248832;
f[892] = 250000;
f[893] = 250047;
f[894] = 250880;
f[895] = 252000;
f[896] = 252105;
f[897] = 253125;
f[898] = 254016;
f[899] = 255150;
f[900] = 256000;
f[901] = 257250;
f[902] = 258048;
f[903] = 259200;
f[904] = 259308;
f[905] = 262144;
f[906] = 262440;
f[907] = 262500;
f[908] = 263424;
f[909] = 264600;
f[910] = 268800;
f[911] = 268912;
f[912] = 270000;
f[913] = 272160;
f[914] = 273375;
f[915] = 274400;
f[916] = 275562;
f[917] = 275625;
f[918] = 276480;
f[919] = 277830;
f[920] = 279936;
f[921] = 280000;
f[922] = 281250;
f[923] = 282240;
f[924] = 283500;
f[925] = 285768;
f[926] = 286720;
f[927] = 288000;
f[928] = 288120;
f[929] = 290304;
f[930] = 291600;
f[931] = 294000;
f[932] = 294912;
f[933] = 295245;
f[934] = 296352;
f[935] = 297675;
f[936] = 300000;
f[937] = 300125;
f[938] = 301056;
f[939] = 302400;
f[940] = 302526;
f[941] = 303750;
f[942] = 306180;
f[943] = 306250;
f[944] = 307200;
f[945] = 307328;
f[946] = 308700;
f[947] = 311040;
f[948] = 312500;
f[949] = 313600;
f[950] = 314928;
f[951] = 315000;
f[952] = 317520;
f[953] = 320000;
f[954] = 321489;
f[955] = 322560;
f[956] = 324000;
f[957] = 324135;
f[958] = 326592;
f[959] = 327680;
f[960] = 328050;
f[961] = 328125;
f[962] = 329280;
f[963] = 330750;
f[964] = 331776;
f[965] = 333396;
f[966] = 336000;
f[967] = 336140;
f[968] = 337500;
f[969] = 338688;
f[970] = 340200;
f[971] = 343000;
f[972] = 344064;
f[973] = 345600;
f[974] = 345744;
f[975] = 349920;
f[976] = 350000;
f[977] = 351232;
f[978] = 352800;
f[979] = 352947;
f[980] = 354294;
f[981] = 354375;
f[982] = 357210;
f[983] = 358400;
f[984] = 360000;
f[985] = 360150;
f[986] = 362880;
f[987] = 364500;
f[988] = 367416;
f[989] = 367500;
f[990] = 368640;
f[991] = 370440;
f[992] = 373248;
f[993] = 375000;
f[994] = 376320;
f[995] = 378000;
f[996] = 381024;
f[997] = 382725;
f[998] = 384000;
f[999] = 384160;
f[1000] = 385875;
f[1001] = 387072;
f[1002] = 388800;
f[1003] = 388962;
f[1004] = 390625;
f[1005] = 392000;
f[1006] = 393216;
f[1007] = 393660;
f[1008] = 393750;
f[1009] = 395136;
f[1010] = 396900;
f[1011] = 400000;
f[1012] = 401408;
f[1013] = 403200;
f[1014] = 403368;
f[1015] = 405000;
f[1016] = 408240;
f[1017] = 409600;
f[1018] = 411600;
f[1019] = 413343;
f[1020] = 414720;
f[1021] = 416745;
f[1022] = 419904;
f[1023] = 420000;
f[1024] = 420175;
f[1025] = 421875;
f[1026] = 423360;
f[1027] = 425250;
f[1028] = 428652;
f[1029] = 428750;
f[1030] = 430080;
f[1031] = 432000;
f[1032] = 432180;
f[1033] = 435456;
f[1034] = 437400;
f[1035] = 437500;
f[1036] = 439040;
f[1037] = 441000;
f[1038] = 442368;
f[1039] = 444528;
f[1040] = 448000;
f[1041] = 450000;
f[1042] = 451584;
f[1043] = 453600;
f[1044] = 453789;
f[1045] = 455625;
f[1046] = 458752;
f[1047] = 459270;
f[1048] = 459375;
f[1049] = 460800;
f[1050] = 460992;
f[1051] = 463050;
f[1052] = 466560;
f[1053] = 468750;
f[1054] = 470400;
f[1055] = 470596;
f[1056] = 472392;
f[1057] = 472500;
f[1058] = 476280;
f[1059] = 480000;
f[1060] = 480200;
f[1061] = 483840;
f[1062] = 486000;
f[1063] = 489888;
f[1064] = 490000;
f[1065] = 491520;
f[1066] = 492075;
f[1067] = 493920;
f[1068] = 496125;
f[1069] = 497664;
f[1070] = 500000;
f[1071] = 500094;
f[1072] = 501760;
f[1073] = 504000;
f[1074] = 504210;
f[1075] = 506250;
f[1076] = 508032;
f[1077] = 510300;
f[1078] = 512000;
f[1079] = 514500;
f[1080] = 516096;
f[1081] = 518400;
f[1082] = 518616;
f[1083] = 524288;
f[1084] = 524880;
f[1085] = 525000;
f[1086] = 526848;
f[1087] = 529200;
f[1088] = 531441;
f[1089] = 535815;
f[1090] = 537600;
f[1091] = 537824;
f[1092] = 540000;
f[1093] = 540225;
f[1094] = 544320;
f[1095] = 546750;
f[1096] = 546875;
f[1097] = 548800;
f[1098] = 551124;
f[1099] = 551250;
f[1100] = 552960;
f[1101] = 555660;
f[1102] = 559872;
f[1103] = 560000;
f[1104] = 562500;
f[1105] = 564480;
f[1106] = 567000;
f[1107] = 571536;
f[1108] = 573440;
f[1109] = 576000;
f[1110] = 576240;
f[1111] = 580608;
f[1112] = 583200;
f[1113] = 583443;
f[1114] = 588000;
f[1115] = 588245;
f[1116] = 589824;
f[1117] = 590490;
f[1118] = 590625;
f[1119] = 592704;
f[1120] = 595350;
f[1121] = 600000;
f[1122] = 600250;
f[1123] = 602112;
f[1124] = 604800;
f[1125] = 605052;
f[1126] = 607500;
f[1127] = 612360;
f[1128] = 612500;
f[1129] = 614400;
f[1130] = 614656;
f[1131] = 617400;
f[1132] = 622080;
f[1133] = 625000;
f[1134] = 627200;
f[1135] = 629856;
f[1136] = 630000;
f[1137] = 635040;
f[1138] = 637875;
f[1139] = 640000;
f[1140] = 642978;
f[1141] = 643125;
f[1142] = 645120;
f[1143] = 648000;
f[1144] = 648270;
f[1145] = 653184;
f[1146] = 655360;
f[1147] = 656100;
f[1148] = 656250;
f[1149] = 658560;
f[1150] = 661500;
f[1151] = 663552;
f[1152] = 666792;
f[1153] = 672000;
f[1154] = 672280;
f[1155] = 675000;
f[1156] = 677376;
f[1157] = 680400;
f[1158] = 686000;
f[1159] = 688128;
f[1160] = 688905;
f[1161] = 691200;
f[1162] = 691488;
f[1163] = 694575;
f[1164] = 699840;
f[1165] = 700000;
f[1166] = 702464;
f[1167] = 703125;
f[1168] = 705600;
f[1169] = 705894;
f[1170] = 708588;
f[1171] = 708750;
f[1172] = 714420;
f[1173] = 716800;
f[1174] = 720000;
f[1175] = 720300;
f[1176] = 725760;
f[1177] = 729000;
f[1178] = 734832;
f[1179] = 735000;
f[1180] = 737280;
f[1181] = 740880;
f[1182] = 746496;
f[1183] = 750000;
f[1184] = 750141;
f[1185] = 752640;
f[1186] = 756000;
f[1187] = 756315;
f[1188] = 759375;
f[1189] = 762048;
f[1190] = 765450;
f[1191] = 765625;
f[1192] = 768000;
f[1193] = 768320;
f[1194] = 771750;
f[1195] = 774144;
f[1196] = 777600;
f[1197] = 777924;
f[1198] = 781250;
f[1199] = 784000;
f[1200] = 786432;
f[1201] = 787320;
f[1202] = 787500;
f[1203] = 790272;
f[1204] = 793800;
f[1205] = 800000;
f[1206] = 802816;
f[1207] = 806400;
f[1208] = 806736;
f[1209] = 810000;
f[1210] = 816480;
f[1211] = 819200;
f[1212] = 820125;
f[1213] = 823200;
f[1214] = 823543;
f[1215] = 826686;
f[1216] = 826875;
f[1217] = 829440;
f[1218] = 833490;
f[1219] = 839808;
f[1220] = 840000;
f[1221] = 840350;
f[1222] = 843750;
f[1223] = 846720;
f[1224] = 850500;
f[1225] = 857304;
f[1226] = 857500;
f[1227] = 860160;
f[1228] = 864000;
f[1229] = 864360;
f[1230] = 870912;
f[1231] = 874800;
f[1232] = 875000;
f[1233] = 878080;
f[1234] = 882000;
f[1235] = 884736;
f[1236] = 885735;
f[1237] = 889056;
f[1238] = 893025;
f[1239] = 896000;
f[1240] = 900000;
f[1241] = 900375;
f[1242] = 903168;
f[1243] = 907200;
f[1244] = 907578;
f[1245] = 911250;
f[1246] = 917504;
f[1247] = 918540;
f[1248] = 918750;
f[1249] = 921600;
f[1250] = 921984;
f[1251] = 926100;
f[1252] = 933120;
f[1253] = 937500;
f[1254] = 940800;
f[1255] = 941192;
f[1256] = 944784;
f[1257] = 945000;
f[1258] = 952560;
f[1259] = 960000;
f[1260] = 960400;
f[1261] = 964467;
f[1262] = 967680;
f[1263] = 972000;
f[1264] = 972405;
f[1265] = 979776;
f[1266] = 980000;
f[1267] = 983040;
f[1268] = 984150;
f[1269] = 984375;
f[1270] = 987840;
f[1271] = 992250;
f[1272] = 995328;
f[1273] = 1000000;
f[1274] = 1000188;
f[1275] = 1003520;
f[1276] = 1008000;
f[1277] = 1008420;
f[1278] = 1012500;
f[1279] = 1016064;
f[1280] = 1020600;
f[1281] = 1024000;
f[1282] = 1029000;
f[1283] = 1032192;
f[1284] = 1036800;
f[1285] = 1037232;
f[1286] = 1048576;
f[1287] = 1049760;
f[1288] = 1050000;
f[1289] = 1053696;
f[1290] = 1058400;
f[1291] = 1058841;
f[1292] = 1062882;
f[1293] = 1063125;
f[1294] = 1071630;
f[1295] = 1071875;
f[1296] = 1075200;
f[1297] = 1075648;
f[1298] = 1080000;
f[1299] = 1080450;
f[1300] = 1088640;
f[1301] = 1093500;
f[1302] = 1093750;
f[1303] = 1097600;
f[1304] = 1102248;
f[1305] = 1102500;
f[1306] = 1105920;
f[1307] = 1111320;
f[1308] = 1119744;
f[1309] = 1120000;
f[1310] = 1125000;
f[1311] = 1128960;
f[1312] = 1134000;
f[1313] = 1143072;
f[1314] = 1146880;
f[1315] = 1148175;
f[1316] = 1152000;
f[1317] = 1152480;
f[1318] = 1157625;
f[1319] = 1161216;
f[1320] = 1166400;
f[1321] = 1166886;
f[1322] = 1171875;
f[1323] = 1176000;
f[1324] = 1176490;
f[1325] = 1179648;
f[1326] = 1180980;
f[1327] = 1181250;
f[1328] = 1185408;
f[1329] = 1190700;
f[1330] = 1200000;
f[1331] = 1200500;
f[1332] = 1204224;
f[1333] = 1209600;
f[1334] = 1210104;
f[1335] = 1215000;
f[1336] = 1224720;
f[1337] = 1225000;
f[1338] = 1228800;
f[1339] = 1229312;
f[1340] = 1234800;
f[1341] = 1240029;
f[1342] = 1244160;
f[1343] = 1250000;
f[1344] = 1250235;
f[1345] = 1254400;
f[1346] = 1259712;
f[1347] = 1260000;
f[1348] = 1260525;
f[1349] = 1265625;
f[1350] = 1270080;
f[1351] = 1275750;
f[1352] = 1280000;
f[1353] = 1285956;
f[1354] = 1286250;
f[1355] = 1290240;
f[1356] = 1296000;
f[1357] = 1296540;
f[1358] = 1306368;
f[1359] = 1310720;
f[1360] = 1312200;
f[1361] = 1312500;
f[1362] = 1317120;
f[1363] = 1323000;
f[1364] = 1327104;
f[1365] = 1333584;
f[1366] = 1344000;
f[1367] = 1344560;
f[1368] = 1350000;
f[1369] = 1354752;
f[1370] = 1360800;
f[1371] = 1361367;
f[1372] = 1366875;
f[1373] = 1372000;
f[1374] = 1376256;
f[1375] = 1377810;
f[1376] = 1378125;
f[1377] = 1382400;
f[1378] = 1382976;
f[1379] = 1389150;
f[1380] = 1399680;
f[1381] = 1400000;
f[1382] = 1404928;
f[1383] = 1406250;
f[1384] = 1411200;
f[1385] = 1411788;
f[1386] = 1417176;
f[1387] = 1417500;
f[1388] = 1428840;
f[1389] = 1433600;
f[1390] = 1440000;
f[1391] = 1440600;
f[1392] = 1451520;
f[1393] = 1458000;
f[1394] = 1469664;
f[1395] = 1470000;
f[1396] = 1474560;
f[1397] = 1476225;
f[1398] = 1481760;
f[1399] = 1488375;
f[1400] = 1492992;
f[1401] = 1500000;
f[1402] = 1500282;
f[1403] = 1500625;
f[1404] = 1505280;
f[1405] = 1512000;
f[1406] = 1512630;
f[1407] = 1518750;
f[1408] = 1524096;
f[1409] = 1530900;
f[1410] = 1531250;
f[1411] = 1536000;
f[1412] = 1536640;
f[1413] = 1543500;
f[1414] = 1548288;
f[1415] = 1555200;
f[1416] = 1555848;
f[1417] = 1562500;
f[1418] = 1568000;
f[1419] = 1572864;
f[1420] = 1574640;
f[1421] = 1575000;
f[1422] = 1580544;
f[1423] = 1587600;
f[1424] = 1594323;
f[1425] = 1600000;
f[1426] = 1605632;
f[1427] = 1607445;
f[1428] = 1612800;
f[1429] = 1613472;
f[1430] = 1620000;
f[1431] = 1620675;
f[1432] = 1632960;
f[1433] = 1638400;
f[1434] = 1640250;
f[1435] = 1640625;
f[1436] = 1646400;
f[1437] = 1647086;
f[1438] = 1653372;
f[1439] = 1653750;
f[1440] = 1658880;
f[1441] = 1666980;
f[1442] = 1679616;
f[1443] = 1680000;
f[1444] = 1680700;
f[1445] = 1687500;
f[1446] = 1693440;
f[1447] = 1701000;
f[1448] = 1714608;
f[1449] = 1715000;
f[1450] = 1720320;
f[1451] = 1728000;
f[1452] = 1728720;
f[1453] = 1741824;
f[1454] = 1749600;
f[1455] = 1750000;
f[1456] = 1750329;
f[1457] = 1756160;
f[1458] = 1764000;
f[1459] = 1764735;
f[1460] = 1769472;
f[1461] = 1771470;
f[1462] = 1771875;
f[1463] = 1778112;
f[1464] = 1786050;
f[1465] = 1792000;
f[1466] = 1800000;
f[1467] = 1800750;
f[1468] = 1806336;
f[1469] = 1814400;
f[1470] = 1815156;
f[1471] = 1822500;
f[1472] = 1835008;
f[1473] = 1837080;
f[1474] = 1837500;
f[1475] = 1843200;
f[1476] = 1843968;
f[1477] = 1852200;
f[1478] = 1866240;
f[1479] = 1875000;
f[1480] = 1881600;
f[1481] = 1882384;
f[1482] = 1889568;
f[1483] = 1890000;
f[1484] = 1905120;
f[1485] = 1913625;
f[1486] = 1920000;
f[1487] = 1920800;
f[1488] = 1928934;
f[1489] = 1929375;
f[1490] = 1935360;
f[1491] = 1944000;
f[1492] = 1944810;
f[1493] = 1953125;
f[1494] = 1959552;
f[1495] = 1960000;
f[1496] = 1966080;
f[1497] = 1968300;
f[1498] = 1968750;
f[1499] = 1975680;
f[1500] = 1984500;
f[1501] = 1990656;
f[1502] = 2000000;
f[1503] = 2000376;
f[1504] = 2007040;
f[1505] = 2016000;
f[1506] = 2016840;
f[1507] = 2025000;
f[1508] = 2032128;
f[1509] = 2041200;
f[1510] = 2048000;
f[1511] = 2058000;
f[1512] = 2064384;
f[1513] = 2066715;
f[1514] = 2073600;
f[1515] = 2074464;
f[1516] = 2083725;
f[1517] = 2097152;
f[1518] = 2099520;
f[1519] = 2100000;
f[1520] = 2100875;
f[1521] = 2107392;
f[1522] = 2109375;
f[1523] = 2116800;
f[1524] = 2117682;
f[1525] = 2125764;
f[1526] = 2126250;
f[1527] = 2143260;
f[1528] = 2143750;
f[1529] = 2150400;
f[1530] = 2151296;
f[1531] = 2160000;
f[1532] = 2160900;
f[1533] = 2177280;
f[1534] = 2187000;
f[1535] = 2187500;
f[1536] = 2195200;
f[1537] = 2204496;
f[1538] = 2205000;
f[1539] = 2211840;
f[1540] = 2222640;
f[1541] = 2239488;
f[1542] = 2240000;
f[1543] = 2250000;
f[1544] = 2250423;
f[1545] = 2257920;
f[1546] = 2268000;
f[1547] = 2268945;
f[1548] = 2278125;
f[1549] = 2286144;
f[1550] = 2293760;
f[1551] = 2296350;
f[1552] = 2296875;
f[1553] = 2304000;
f[1554] = 2304960;
f[1555] = 2315250;
f[1556] = 2322432;
f[1557] = 2332800;
f[1558] = 2333772;
f[1559] = 2343750;
f[1560] = 2352000;
f[1561] = 2352980;
f[1562] = 2359296;
f[1563] = 2361960;
f[1564] = 2362500;
f[1565] = 2370816;
f[1566] = 2381400;
f[1567] = 2400000;
f[1568] = 2401000;
f[1569] = 2408448;
f[1570] = 2419200;
f[1571] = 2420208;
f[1572] = 2430000;
f[1573] = 2449440;
f[1574] = 2450000;
f[1575] = 2457600;
f[1576] = 2458624;
f[1577] = 2460375;
f[1578] = 2469600;
f[1579] = 2470629;
f[1580] = 2480058;
f[1581] = 2480625;
f[1582] = 2488320;
f[1583] = 2500000;
f[1584] = 2500470;
f[1585] = 2508800;
f[1586] = 2519424;
f[1587] = 2520000;
f[1588] = 2521050;
f[1589] = 2531250;
f[1590] = 2540160;
f[1591] = 2551500;
f[1592] = 2560000;
f[1593] = 2571912;
f[1594] = 2572500;
f[1595] = 2580480;
f[1596] = 2592000;
f[1597] = 2593080;
f[1598] = 2612736;
f[1599] = 2621440;
f[1600] = 2624400;
f[1601] = 2625000;
f[1602] = 2634240;
f[1603] = 2646000;
f[1604] = 2654208;
f[1605] = 2657205;
f[1606] = 2667168;
f[1607] = 2679075;
f[1608] = 2688000;
f[1609] = 2689120;
f[1610] = 2700000;
f[1611] = 2701125;
f[1612] = 2709504;
f[1613] = 2721600;
f[1614] = 2722734;
f[1615] = 2733750;
f[1616] = 2734375;
f[1617] = 2744000;
f[1618] = 2752512;
f[1619] = 2755620;
f[1620] = 2756250;
f[1621] = 2764800;
f[1622] = 2765952;
f[1623] = 2778300;
f[1624] = 2799360;
f[1625] = 2800000;
f[1626] = 2809856;
f[1627] = 2812500;
f[1628] = 2822400;
f[1629] = 2823576;
f[1630] = 2834352;
f[1631] = 2835000;
f[1632] = 2857680;
f[1633] = 2867200;
f[1634] = 2880000;
f[1635] = 2881200;
f[1636] = 2893401;
f[1637] = 2903040;
f[1638] = 2916000;
f[1639] = 2917215;
f[1640] = 2939328;
f[1641] = 2940000;
f[1642] = 2941225;
f[1643] = 2949120;
f[1644] = 2952450;
f[1645] = 2953125;
f[1646] = 2963520;
f[1647] = 2976750;
f[1648] = 2985984;
f[1649] = 3000000;
f[1650] = 3000564;
f[1651] = 3001250;
f[1652] = 3010560;
f[1653] = 3024000;
f[1654] = 3025260;
f[1655] = 3037500;
f[1656] = 3048192;
f[1657] = 3061800;
f[1658] = 3062500;
f[1659] = 3072000;
f[1660] = 3073280;
f[1661] = 3087000;
f[1662] = 3096576;
f[1663] = 3110400;
f[1664] = 3111696;
f[1665] = 3125000;
f[1666] = 3136000;
f[1667] = 3145728;
f[1668] = 3149280;
f[1669] = 3150000;
f[1670] = 3161088;
f[1671] = 3175200;
f[1672] = 3176523;
f[1673] = 3188646;
f[1674] = 3189375;
f[1675] = 3200000;
f[1676] = 3211264;
f[1677] = 3214890;
f[1678] = 3215625;
f[1679] = 3225600;
f[1680] = 3226944;
f[1681] = 3240000;
f[1682] = 3241350;
f[1683] = 3265920;
f[1684] = 3276800;
f[1685] = 3280500;
f[1686] = 3281250;
f[1687] = 3292800;
f[1688] = 3294172;
f[1689] = 3306744;
f[1690] = 3307500;
f[1691] = 3317760;
f[1692] = 3333960;
f[1693] = 3359232;
f[1694] = 3360000;
f[1695] = 3361400;
f[1696] = 3375000;
f[1697] = 3386880;
f[1698] = 3402000;
f[1699] = 3429216;
f[1700] = 3430000;
f[1701] = 3440640;
f[1702] = 3444525;
f[1703] = 3456000;
f[1704] = 3457440;
f[1705] = 3472875;
f[1706] = 3483648;
f[1707] = 3499200;
f[1708] = 3500000;
f[1709] = 3500658;
f[1710] = 3512320;
f[1711] = 3515625;
f[1712] = 3528000;
f[1713] = 3529470;
f[1714] = 3538944;
f[1715] = 3542940;
f[1716] = 3543750;
f[1717] = 3556224;
f[1718] = 3572100;
f[1719] = 3584000;
f[1720] = 3600000;
f[1721] = 3601500;
f[1722] = 3612672;
f[1723] = 3628800;
f[1724] = 3630312;
f[1725] = 3645000;
f[1726] = 3670016;
f[1727] = 3674160;
f[1728] = 3675000;
f[1729] = 3686400;
f[1730] = 3687936;
f[1731] = 3704400;
f[1732] = 3720087;
f[1733] = 3732480;
f[1734] = 3750000;
f[1735] = 3750705;
f[1736] = 3763200;
f[1737] = 3764768;
f[1738] = 3779136;
f[1739] = 3780000;
f[1740] = 3781575;
f[1741] = 3796875;
f[1742] = 3810240;
f[1743] = 3827250;
f[1744] = 3828125;
f[1745] = 3840000;
f[1746] = 3841600;
f[1747] = 3857868;
f[1748] = 3858750;
f[1749] = 3870720;
f[1750] = 3888000;
f[1751] = 3889620;
f[1752] = 3906250;
f[1753] = 3919104;
f[1754] = 3920000;
f[1755] = 3932160;
f[1756] = 3936600;
f[1757] = 3937500;
f[1758] = 3951360;
f[1759] = 3969000;
f[1760] = 3981312;
f[1761] = 4000000;
f[1762] = 4000752;
f[1763] = 4014080;
f[1764] = 4032000;
f[1765] = 4033680;
f[1766] = 4050000;
f[1767] = 4064256;
f[1768] = 4082400;
f[1769] = 4084101;
f[1770] = 4096000;
f[1771] = 4100625;
f[1772] = 4116000;
f[1773] = 4117715;
f[1774] = 4128768;
f[1775] = 4133430;
f[1776] = 4134375;
f[1777] = 4147200;
f[1778] = 4148928;
f[1779] = 4167450;
f[1780] = 4194304;
f[1781] = 4199040;
f[1782] = 4200000;
f[1783] = 4201750;
f[1784] = 4214784;
f[1785] = 4218750;
f[1786] = 4233600;
f[1787] = 4235364;
f[1788] = 4251528;
f[1789] = 4252500;
f[1790] = 4286520;
f[1791] = 4287500;
f[1792] = 4300800;
f[1793] = 4302592;
f[1794] = 4320000;
f[1795] = 4321800;
f[1796] = 4354560;
f[1797] = 4374000;
f[1798] = 4375000;
f[1799] = 4390400;
f[1800] = 4408992;
f[1801] = 4410000;
f[1802] = 4423680;
f[1803] = 4428675;
f[1804] = 4445280;
f[1805] = 4465125;
f[1806] = 4478976;
f[1807] = 4480000;
f[1808] = 4500000;
f[1809] = 4500846;
f[1810] = 4501875;
f[1811] = 4515840;
f[1812] = 4536000;
f[1813] = 4537890;
f[1814] = 4556250;
f[1815] = 4572288;
f[1816] = 4587520;
f[1817] = 4592700;
f[1818] = 4593750;
f[1819] = 4608000;
f[1820] = 4609920;
f[1821] = 4630500;
f[1822] = 4644864;
f[1823] = 4665600;
f[1824] = 4667544;
f[1825] = 4687500;
f[1826] = 4704000;
f[1827] = 4705960;
f[1828] = 4718592;
f[1829] = 4723920;
f[1830] = 4725000;
f[1831] = 4741632;
f[1832] = 4762800;
f[1833] = 4782969;
f[1834] = 4800000;
f[1835] = 4802000;
f[1836] = 4816896;
f[1837] = 4822335;
f[1838] = 4838400;
f[1839] = 4840416;
f[1840] = 4860000;
f[1841] = 4862025;
f[1842] = 4898880;
f[1843] = 4900000;
f[1844] = 4915200;
f[1845] = 4917248;
f[1846] = 4920750;
f[1847] = 4921875;
f[1848] = 4939200;
f[1849] = 4941258;
f[1850] = 4960116;
f[1851] = 4961250;
f[1852] = 4976640;
f[1853] = 5000000;
f[1854] = 5000940;
f[1855] = 5017600;
f[1856] = 5038848;
f[1857] = 5040000;
f[1858] = 5042100;
f[1859] = 5062500;
f[1860] = 5080320;
f[1861] = 5103000;
f[1862] = 5120000;
f[1863] = 5143824;
f[1864] = 5145000;
f[1865] = 5160960;
f[1866] = 5184000;
f[1867] = 5186160;
f[1868] = 5225472;
f[1869] = 5242880;
f[1870] = 5248800;
f[1871] = 5250000;
f[1872] = 5250987;
f[1873] = 5268480;
f[1874] = 5292000;
f[1875] = 5294205;
f[1876] = 5308416;
f[1877] = 5314410;
f[1878] = 5315625;
f[1879] = 5334336;
f[1880] = 5358150;
f[1881] = 5359375;
f[1882] = 5376000;
f[1883] = 5378240;
f[1884] = 5400000;
f[1885] = 5402250;
f[1886] = 5419008;
f[1887] = 5443200;
f[1888] = 5445468;
f[1889] = 5467500;
f[1890] = 5468750;
f[1891] = 5488000;
f[1892] = 5505024;
f[1893] = 5511240;
f[1894] = 5512500;
f[1895] = 5529600;
f[1896] = 5531904;
f[1897] = 5556600;
f[1898] = 5598720;
f[1899] = 5600000;
f[1900] = 5619712;
f[1901] = 5625000;
f[1902] = 5644800;
f[1903] = 5647152;
f[1904] = 5668704;
f[1905] = 5670000;
f[1906] = 5715360;
f[1907] = 5734400;
f[1908] = 5740875;
f[1909] = 5760000;
f[1910] = 5762400;
f[1911] = 5764801;
f[1912] = 5786802;
f[1913] = 5788125;
f[1914] = 5806080;
f[1915] = 5832000;
f[1916] = 5834430;
f[1917] = 5859375;
f[1918] = 5878656;
f[1919] = 5880000;
f[1920] = 5882450;
f[1921] = 5898240;
f[1922] = 5904900;
f[1923] = 5906250;
f[1924] = 5927040;
f[1925] = 5953500;
f[1926] = 5971968;
f[1927] = 6000000;
f[1928] = 6001128;
f[1929] = 6002500;
f[1930] = 6021120;
f[1931] = 6048000;
f[1932] = 6050520;
f[1933] = 6075000;
f[1934] = 6096384;
f[1935] = 6123600;
f[1936] = 6125000;
f[1937] = 6144000;
f[1938] = 6146560;
f[1939] = 6174000;
f[1940] = 6193152;
f[1941] = 6200145;
f[1942] = 6220800;
f[1943] = 6223392;
f[1944] = 6250000;
f[1945] = 6251175;
f[1946] = 6272000;
f[1947] = 6291456;
f[1948] = 6298560;
f[1949] = 6300000;
f[1950] = 6302625;
f[1951] = 6322176;
f[1952] = 6328125;
f[1953] = 6350400;
f[1954] = 6353046;
f[1955] = 6377292;
f[1956] = 6378750;
f[1957] = 6400000;
f[1958] = 6422528;
f[1959] = 6429780;
f[1960] = 6431250;
f[1961] = 6451200;
f[1962] = 6453888;
f[1963] = 6480000;
f[1964] = 6482700;
f[1965] = 6531840;
f[1966] = 6553600;
f[1967] = 6561000;
f[1968] = 6562500;
f[1969] = 6585600;
f[1970] = 6588344;
f[1971] = 6613488;
f[1972] = 6615000;
f[1973] = 6635520;
f[1974] = 6667920;
f[1975] = 6718464;
f[1976] = 6720000;
f[1977] = 6722800;
f[1978] = 6750000;
f[1979] = 6751269;
f[1980] = 6773760;
f[1981] = 6804000;
f[1982] = 6806835;
f[1983] = 6834375;
f[1984] = 6858432;
f[1985] = 6860000;
f[1986] = 6881280;
f[1987] = 6889050;
f[1988] = 6890625;
f[1989] = 6912000;
f[1990] = 6914880;
f[1991] = 6945750;
f[1992] = 6967296;
f[1993] = 6998400;
f[1994] = 7000000;
f[1995] = 7001316;
f[1996] = 7024640;
f[1997] = 7031250;
f[1998] = 7056000;
f[1999] = 7058940;
f[2000] = 7077888;
f[2001] = 7085880;
f[2002] = 7087500;
f[2003] = 7112448;
f[2004] = 7144200;
f[2005] = 7168000;
f[2006] = 7200000;
f[2007] = 7203000;
f[2008] = 7225344;
f[2009] = 7257600;
f[2010] = 7260624;
f[2011] = 7290000;
f[2012] = 7340032;
f[2013] = 7348320;
f[2014] = 7350000;
f[2015] = 7372800;
f[2016] = 7375872;
f[2017] = 7381125;
f[2018] = 7408800;
f[2019] = 7411887;
f[2020] = 7440174;
f[2021] = 7441875;
f[2022] = 7464960;
f[2023] = 7500000;
f[2024] = 7501410;
f[2025] = 7503125;
f[2026] = 7526400;
f[2027] = 7529536;
f[2028] = 7558272;
f[2029] = 7560000;
f[2030] = 7563150;
f[2031] = 7593750;
f[2032] = 7620480;
f[2033] = 7654500;
f[2034] = 7656250;
f[2035] = 7680000;
f[2036] = 7683200;
f[2037] = 7715736;
f[2038] = 7717500;
f[2039] = 7741440;
f[2040] = 7776000;
f[2041] = 7779240;
f[2042] = 7812500;
f[2043] = 7838208;
f[2044] = 7840000;
f[2045] = 7864320;
f[2046] = 7873200;
f[2047] = 7875000;
f[2048] = 7902720;
f[2049] = 7938000;
f[2050] = 7962624;
f[2051] = 7971615;
f[2052] = 8000000;
f[2053] = 8001504;
f[2054] = 8028160;
f[2055] = 8037225;
f[2056] = 8064000;
f[2057] = 8067360;
f[2058] = 8100000;
f[2059] = 8103375;
f[2060] = 8128512;
f[2061] = 8164800;
f[2062] = 8168202;
f[2063] = 8192000;
f[2064] = 8201250;
f[2065] = 8203125;
f[2066] = 8232000;
f[2067] = 8235430;
f[2068] = 8257536;
f[2069] = 8266860;
f[2070] = 8268750;
f[2071] = 8294400;
f[2072] = 8297856;
f[2073] = 8334900;
f[2074] = 8388608;
f[2075] = 8398080;
f[2076] = 8400000;
f[2077] = 8403500;
f[2078] = 8429568;
f[2079] = 8437500;
f[2080] = 8467200;
f[2081] = 8470728;
f[2082] = 8503056;
f[2083] = 8505000;
f[2084] = 8573040;
f[2085] = 8575000;
f[2086] = 8601600;
f[2087] = 8605184;
f[2088] = 8640000;
f[2089] = 8643600;
f[2090] = 8680203;
f[2091] = 8709120;
f[2092] = 8748000;
f[2093] = 8750000;
f[2094] = 8751645;
f[2095] = 8780800;
f[2096] = 8817984;
f[2097] = 8820000;
f[2098] = 8823675;
f[2099] = 8847360;
f[2100] = 8857350;
f[2101] = 8859375;
f[2102] = 8890560;
f[2103] = 8930250;
f[2104] = 8957952;
f[2105] = 8960000;
f[2106] = 9000000;
f[2107] = 9001692;
f[2108] = 9003750;
f[2109] = 9031680;
f[2110] = 9072000;
f[2111] = 9075780;
f[2112] = 9112500;
f[2113] = 9144576;
f[2114] = 9175040;
f[2115] = 9185400;
f[2116] = 9187500;
f[2117] = 9216000;
f[2118] = 9219840;
f[2119] = 9261000;
f[2120] = 9289728;
f[2121] = 9331200;
f[2122] = 9335088;
f[2123] = 9375000;
f[2124] = 9408000;
f[2125] = 9411920;
f[2126] = 9437184;
f[2127] = 9447840;
f[2128] = 9450000;
f[2129] = 9483264;
f[2130] = 9525600;
f[2131] = 9529569;
f[2132] = 9565938;
f[2133] = 9568125;
f[2134] = 9600000;
f[2135] = 9604000;
f[2136] = 9633792;
f[2137] = 9644670;
f[2138] = 9646875;
f[2139] = 9676800;
f[2140] = 9680832;
f[2141] = 9720000;
f[2142] = 9724050;
f[2143] = 9765625;
f[2144] = 9797760;
f[2145] = 9800000;
f[2146] = 9830400;
f[2147] = 9834496;
f[2148] = 9841500;
f[2149] = 9843750;
f[2150] = 9878400;
f[2151] = 9882516;
f[2152] = 9920232;
f[2153] = 9922500;
f[2154] = 9953280;
f[2155] = 10000000;
f[2156] = 10001880;
f[2157] = 10035200;
f[2158] = 10077696;
f[2159] = 10080000;
f[2160] = 10084200;
f[2161] = 10125000;
f[2162] = 10160640;
f[2163] = 10206000;
f[2164] = 10240000;
f[2165] = 10287648;
f[2166] = 10290000;
f[2167] = 10321920;
f[2168] = 10333575;
f[2169] = 10368000;
f[2170] = 10372320;
f[2171] = 10418625;
f[2172] = 10450944;
f[2173] = 10485760;
f[2174] = 10497600;
f[2175] = 10500000;
f[2176] = 10501974;
f[2177] = 10504375;
f[2178] = 10536960;
f[2179] = 10546875;
f[2180] = 10584000;
f[2181] = 10588410;
f[2182] = 10616832;
f[2183] = 10628820;
f[2184] = 10631250;
f[2185] = 10668672;
f[2186] = 10716300;
f[2187] = 10718750;
f[2188] = 10752000;
f[2189] = 10756480;
f[2190] = 10800000;
f[2191] = 10804500;
f[2192] = 10838016;
f[2193] = 10886400;
f[2194] = 10890936;
f[2195] = 10935000;
f[2196] = 10937500;
f[2197] = 10976000;
f[2198] = 11010048;
f[2199] = 11022480;
f[2200] = 11025000;
f[2201] = 11059200;
f[2202] = 11063808;
f[2203] = 11113200;
f[2204] = 11160261;
f[2205] = 11197440;
f[2206] = 11200000;
f[2207] = 11239424;
f[2208] = 11250000;
f[2209] = 11252115;
f[2210] = 11289600;
f[2211] = 11294304;
f[2212] = 11337408;
f[2213] = 11340000;
f[2214] = 11344725;
f[2215] = 11390625;
f[2216] = 11430720;
f[2217] = 11468800;
f[2218] = 11481750;
f[2219] = 11484375;
f[2220] = 11520000;
f[2221] = 11524800;
f[2222] = 11529602;
f[2223] = 11573604;
f[2224] = 11576250;
f[2225] = 11612160;
f[2226] = 11664000;
f[2227] = 11668860;
f[2228] = 11718750;
f[2229] = 11757312;
f[2230] = 11760000;
f[2231] = 11764900;
f[2232] = 11796480;
f[2233] = 11809800;
f[2234] = 11812500;
f[2235] = 11854080;
f[2236] = 11907000;
f[2237] = 11943936;
f[2238] = 12000000;
f[2239] = 12002256;
f[2240] = 12005000;
f[2241] = 12042240;
f[2242] = 12096000;
f[2243] = 12101040;
f[2244] = 12150000;
f[2245] = 12192768;
f[2246] = 12247200;
f[2247] = 12250000;
f[2248] = 12252303;
f[2249] = 12288000;
f[2250] = 12293120;
f[2251] = 12301875;
f[2252] = 12348000;
f[2253] = 12353145;
f[2254] = 12386304;
f[2255] = 12400290;
f[2256] = 12403125;
f[2257] = 12441600;
f[2258] = 12446784;
f[2259] = 12500000;
f[2260] = 12502350;
f[2261] = 12544000;
f[2262] = 12582912;
f[2263] = 12597120;
f[2264] = 12600000;
f[2265] = 12605250;
f[2266] = 12644352;
f[2267] = 12656250;
f[2268] = 12700800;
f[2269] = 12706092;
f[2270] = 12754584;
f[2271] = 12757500;
f[2272] = 12800000;
f[2273] = 12845056;
f[2274] = 12859560;
f[2275] = 12862500;
f[2276] = 12902400;
f[2277] = 12907776;
f[2278] = 12960000;
f[2279] = 12965400;
f[2280] = 13063680;
f[2281] = 13107200;
f[2282] = 13122000;
f[2283] = 13125000;
f[2284] = 13171200;
f[2285] = 13176688;
f[2286] = 13226976;
f[2287] = 13230000;
f[2288] = 13271040;
f[2289] = 13286025;
f[2290] = 13335840;
f[2291] = 13395375;
f[2292] = 13436928;
f[2293] = 13440000;
f[2294] = 13445600;
f[2295] = 13500000;
f[2296] = 13502538;
f[2297] = 13505625;
f[2298] = 13547520;
f[2299] = 13608000;
f[2300] = 13613670;
f[2301] = 13668750;
f[2302] = 13671875;
f[2303] = 13716864;
f[2304] = 13720000;
f[2305] = 13762560;
f[2306] = 13778100;
f[2307] = 13781250;
f[2308] = 13824000;
f[2309] = 13829760;
f[2310] = 13891500;
f[2311] = 13934592;
f[2312] = 13996800;
f[2313] = 14000000;
f[2314] = 14002632;
f[2315] = 14049280;
f[2316] = 14062500;
f[2317] = 14112000;
f[2318] = 14117880;
f[2319] = 14155776;
f[2320] = 14171760;
f[2321] = 14175000;
f[2322] = 14224896;
f[2323] = 14288400;
f[2324] = 14336000;
f[2325] = 14348907;
f[2326] = 14400000;
f[2327] = 14406000;
f[2328] = 14450688;
f[2329] = 14467005;
f[2330] = 14515200;
f[2331] = 14521248;
f[2332] = 14580000;
f[2333] = 14586075;
f[2334] = 14680064;
f[2335] = 14696640;
f[2336] = 14700000;
f[2337] = 14706125;
f[2338] = 14745600;
f[2339] = 14751744;
f[2340] = 14762250;
f[2341] = 14765625;
f[2342] = 14817600;
f[2343] = 14823774;
f[2344] = 14880348;
f[2345] = 14883750;
f[2346] = 14929920;
f[2347] = 15000000;
f[2348] = 15002820;
f[2349] = 15006250;
f[2350] = 15052800;
f[2351] = 15059072;
f[2352] = 15116544;
f[2353] = 15120000;
f[2354] = 15126300;
f[2355] = 15187500;
f[2356] = 15240960;
f[2357] = 15309000;
f[2358] = 15312500;
f[2359] = 15360000;
f[2360] = 15366400;
f[2361] = 15431472;
f[2362] = 15435000;
f[2363] = 15482880;
f[2364] = 15552000;
f[2365] = 15558480;
f[2366] = 15625000;
f[2367] = 15676416;
f[2368] = 15680000;
f[2369] = 15728640;
f[2370] = 15746400;
f[2371] = 15750000;
f[2372] = 15752961;
f[2373] = 15805440;
f[2374] = 15876000;
f[2375] = 15882615;
f[2376] = 15925248;
f[2377] = 15943230;
f[2378] = 15946875;
f[2379] = 16000000;
f[2380] = 16003008;
f[2381] = 16056320;
f[2382] = 16074450;
f[2383] = 16078125;
f[2384] = 16128000;
f[2385] = 16134720;
f[2386] = 16200000;
f[2387] = 16206750;
f[2388] = 16257024;
f[2389] = 16329600;
f[2390] = 16336404;
f[2391] = 16384000;
f[2392] = 16402500;
f[2393] = 16406250;
f[2394] = 16464000;
f[2395] = 16470860;
f[2396] = 16515072;
f[2397] = 16533720;
f[2398] = 16537500;
f[2399] = 16588800;
f[2400] = 16595712;
f[2401] = 16669800;
f[2402] = 16777216;
f[2403] = 16796160;
f[2404] = 16800000;
f[2405] = 16807000;
f[2406] = 16859136;
f[2407] = 16875000;
f[2408] = 16934400;
f[2409] = 16941456;
f[2410] = 17006112;
f[2411] = 17010000;
f[2412] = 17146080;
f[2413] = 17150000;
f[2414] = 17203200;
f[2415] = 17210368;
f[2416] = 17222625;
f[2417] = 17280000;
f[2418] = 17287200;
f[2419] = 17294403;
f[2420] = 17360406;
f[2421] = 17364375;
f[2422] = 17418240;
f[2423] = 17496000;
f[2424] = 17500000;
f[2425] = 17503290;
f[2426] = 17561600;
f[2427] = 17578125;
f[2428] = 17635968;
f[2429] = 17640000;
f[2430] = 17647350;
f[2431] = 17694720;
f[2432] = 17714700;
f[2433] = 17718750;
f[2434] = 17781120;
f[2435] = 17860500;
f[2436] = 17915904;
f[2437] = 17920000;
f[2438] = 18000000;
f[2439] = 18003384;
f[2440] = 18007500;
f[2441] = 18063360;
f[2442] = 18144000;
f[2443] = 18151560;
f[2444] = 18225000;
f[2445] = 18289152;
f[2446] = 18350080;
f[2447] = 18370800;
f[2448] = 18375000;
f[2449] = 18432000;
f[2450] = 18439680;
f[2451] = 18522000;
f[2452] = 18579456;
f[2453] = 18600435;
f[2454] = 18662400;
f[2455] = 18670176;
f[2456] = 18750000;
f[2457] = 18753525;
f[2458] = 18816000;
f[2459] = 18823840;
f[2460] = 18874368;
f[2461] = 18895680;
f[2462] = 18900000;
f[2463] = 18907875;
f[2464] = 18966528;
f[2465] = 18984375;
f[2466] = 19051200;
f[2467] = 19059138;
f[2468] = 19131876;
f[2469] = 19136250;
f[2470] = 19140625;
f[2471] = 19200000;
f[2472] = 19208000;
f[2473] = 19267584;
f[2474] = 19289340;
f[2475] = 19293750;
f[2476] = 19353600;
f[2477] = 19361664;
f[2478] = 19440000;
f[2479] = 19448100;
f[2480] = 19531250;
f[2481] = 19595520;
f[2482] = 19600000;
f[2483] = 19660800;
f[2484] = 19668992;
f[2485] = 19683000;
f[2486] = 19687500;
f[2487] = 19756800;
f[2488] = 19765032;
f[2489] = 19840464;
f[2490] = 19845000;
f[2491] = 19906560;
f[2492] = 20000000;
f[2493] = 20003760;
f[2494] = 20070400;
f[2495] = 20155392;
f[2496] = 20160000;
f[2497] = 20168400;
f[2498] = 20250000;
f[2499] = 20253807;
f[2500] = 20321280;
f[2501] = 20412000;
f[2502] = 20420505;
f[2503] = 20480000;
f[2504] = 20503125;
f[2505] = 20575296;
f[2506] = 20580000;
f[2507] = 20588575;
f[2508] = 20643840;
f[2509] = 20667150;
f[2510] = 20671875;
f[2511] = 20736000;
f[2512] = 20744640;
f[2513] = 20837250;
f[2514] = 20901888;
f[2515] = 20971520;
f[2516] = 20995200;
f[2517] = 21000000;
f[2518] = 21003948;
f[2519] = 21008750;
f[2520] = 21073920;
f[2521] = 21093750;
f[2522] = 21168000;
f[2523] = 21176820;
f[2524] = 21233664;
f[2525] = 21257640;
f[2526] = 21262500;
f[2527] = 21337344;
f[2528] = 21432600;
f[2529] = 21437500;
f[2530] = 21504000;
f[2531] = 21512960;
f[2532] = 21600000;
f[2533] = 21609000;
f[2534] = 21676032;
f[2535] = 21772800;
f[2536] = 21781872;
f[2537] = 21870000;
f[2538] = 21875000;
f[2539] = 21952000;
f[2540] = 22020096;
f[2541] = 22044960;
f[2542] = 22050000;
f[2543] = 22118400;
f[2544] = 22127616;
f[2545] = 22143375;
f[2546] = 22226400;
f[2547] = 22235661;
f[2548] = 22320522;
f[2549] = 22325625;
f[2550] = 22394880;
f[2551] = 22400000;
f[2552] = 22478848;
f[2553] = 22500000;
f[2554] = 22504230;
f[2555] = 22509375;
f[2556] = 22579200;
f[2557] = 22588608;
f[2558] = 22674816;
f[2559] = 22680000;
f[2560] = 22689450;
f[2561] = 22781250;
f[2562] = 22861440;
f[2563] = 22937600;
f[2564] = 22963500;
f[2565] = 22968750;
f[2566] = 23040000;
f[2567] = 23049600;
f[2568] = 23059204;
f[2569] = 23147208;
f[2570] = 23152500;
f[2571] = 23224320;
f[2572] = 23328000;
f[2573] = 23337720;
f[2574] = 23437500;
f[2575] = 23514624;
f[2576] = 23520000;
f[2577] = 23529800;
f[2578] = 23592960;
f[2579] = 23619600;
f[2580] = 23625000;
f[2581] = 23708160;
f[2582] = 23814000;
f[2583] = 23887872;
f[2584] = 23914845;
f[2585] = 24000000;
f[2586] = 24004512;
f[2587] = 24010000;
f[2588] = 24084480;
f[2589] = 24111675;
f[2590] = 24192000;
f[2591] = 24202080;
f[2592] = 24300000;
f[2593] = 24310125;
f[2594] = 24385536;
f[2595] = 24494400;
f[2596] = 24500000;
f[2597] = 24504606;
f[2598] = 24576000;
f[2599] = 24586240;
f[2600] = 24603750;
f[2601] = 24609375;
f[2602] = 24696000;
f[2603] = 24706290;
f[2604] = 24772608;
f[2605] = 24800580;
f[2606] = 24806250;
f[2607] = 24883200;
f[2608] = 24893568;
f[2609] = 25000000;
f[2610] = 25004700;
f[2611] = 25088000;
f[2612] = 25165824;
f[2613] = 25194240;
f[2614] = 25200000;
f[2615] = 25210500;
f[2616] = 25288704;
f[2617] = 25312500;
f[2618] = 25401600;
f[2619] = 25412184;
f[2620] = 25509168;
f[2621] = 25515000;
f[2622] = 25600000;
f[2623] = 25690112;
f[2624] = 25719120;
f[2625] = 25725000;
f[2626] = 25804800;
f[2627] = 25815552;
f[2628] = 25920000;
f[2629] = 25930800;
f[2630] = 26040609;
f[2631] = 26127360;
f[2632] = 26214400;
f[2633] = 26244000;
f[2634] = 26250000;
f[2635] = 26254935;
f[2636] = 26342400;
f[2637] = 26353376;
f[2638] = 26453952;
f[2639] = 26460000;
f[2640] = 26471025;
f[2641] = 26542080;
f[2642] = 26572050;
f[2643] = 26578125;
f[2644] = 26671680;
f[2645] = 26790750;
f[2646] = 26796875;
f[2647] = 26873856;
f[2648] = 26880000;
f[2649] = 26891200;
f[2650] = 27000000;
f[2651] = 27005076;
f[2652] = 27011250;
f[2653] = 27095040;
f[2654] = 27216000;
f[2655] = 27227340;
f[2656] = 27337500;
f[2657] = 27343750;
f[2658] = 27433728;
f[2659] = 27440000;
f[2660] = 27525120;
f[2661] = 27556200;
f[2662] = 27562500;
f[2663] = 27648000;
f[2664] = 27659520;
f[2665] = 27783000;
f[2666] = 27869184;
f[2667] = 27993600;
f[2668] = 28000000;
f[2669] = 28005264;
f[2670] = 28098560;
f[2671] = 28125000;
f[2672] = 28224000;
f[2673] = 28235760;
f[2674] = 28311552;
f[2675] = 28343520;
f[2676] = 28350000;
f[2677] = 28449792;
f[2678] = 28576800;
f[2679] = 28588707;
f[2680] = 28672000;
f[2681] = 28697814;
f[2682] = 28704375;
f[2683] = 28800000;
f[2684] = 28812000;
f[2685] = 28824005;
f[2686] = 28901376;
f[2687] = 28934010;
f[2688] = 28940625;
f[2689] = 29030400;
f[2690] = 29042496;
f[2691] = 29160000;
f[2692] = 29172150;
f[2693] = 29296875;
f[2694] = 29360128;
f[2695] = 29393280;
f[2696] = 29400000;
f[2697] = 29412250;
f[2698] = 29491200;
f[2699] = 29503488;
f[2700] = 29524500;
f[2701] = 29531250;
f[2702] = 29635200;
f[2703] = 29647548;
f[2704] = 29760696;
f[2705] = 29767500;
f[2706] = 29859840;
f[2707] = 30000000;
f[2708] = 30005640;
f[2709] = 30012500;
f[2710] = 30105600;
f[2711] = 30118144;
f[2712] = 30233088;
f[2713] = 30240000;
f[2714] = 30252600;
f[2715] = 30375000;
f[2716] = 30481920;
f[2717] = 30618000;
f[2718] = 30625000;
f[2719] = 30720000;
f[2720] = 30732800;
f[2721] = 30862944;
f[2722] = 30870000;
f[2723] = 30965760;
f[2724] = 31000725;
f[2725] = 31104000;
f[2726] = 31116960;
f[2727] = 31250000;
f[2728] = 31255875;
f[2729] = 31352832;
f[2730] = 31360000;
f[2731] = 31457280;
f[2732] = 31492800;
f[2733] = 31500000;
f[2734] = 31505922;
f[2735] = 31513125;
f[2736] = 31610880;
f[2737] = 31640625;
f[2738] = 31752000;
f[2739] = 31765230;
f[2740] = 31850496;
f[2741] = 31886460;
f[2742] = 31893750;
f[2743] = 32000000;
f[2744] = 32006016;
f[2745] = 32112640;
f[2746] = 32148900;
f[2747] = 32156250;
f[2748] = 32256000;
f[2749] = 32269440;
f[2750] = 32400000;
f[2751] = 32413500;
f[2752] = 32514048;
f[2753] = 32659200;
f[2754] = 32672808;
f[2755] = 32768000;
f[2756] = 32805000;
f[2757] = 32812500;
f[2758] = 32928000;
f[2759] = 32941720;
f[2760] = 33030144;
f[2761] = 33067440;
f[2762] = 33075000;
f[2763] = 33177600;
f[2764] = 33191424;
f[2765] = 33339600;
f[2766] = 33480783;
f[2767] = 33554432;
f[2768] = 33592320;
f[2769] = 33600000;
f[2770] = 33614000;
f[2771] = 33718272;
f[2772] = 33750000;
f[2773] = 33756345;
f[2774] = 33868800;
f[2775] = 33882912;
f[2776] = 34012224;
f[2777] = 34020000;
f[2778] = 34034175;
f[2779] = 34171875;
f[2780] = 34292160;
f[2781] = 34300000;
f[2782] = 34406400;
f[2783] = 34420736;
f[2784] = 34445250;
f[2785] = 34453125;
f[2786] = 34560000;
f[2787] = 34574400;
f[2788] = 34588806;
f[2789] = 34720812;
f[2790] = 34728750;
f[2791] = 34836480;
f[2792] = 34992000;
f[2793] = 35000000;
f[2794] = 35006580;
f[2795] = 35123200;
f[2796] = 35156250;
f[2797] = 35271936;
f[2798] = 35280000;
f[2799] = 35294700;
f[2800] = 35389440;
f[2801] = 35429400;
f[2802] = 35437500;
f[2803] = 35562240;
f[2804] = 35721000;
f[2805] = 35831808;
f[2806] = 35840000;
f[2807] = 36000000;
f[2808] = 36006768;
f[2809] = 36015000;
f[2810] = 36126720;
f[2811] = 36288000;
f[2812] = 36303120;
f[2813] = 36450000;
f[2814] = 36578304;
f[2815] = 36700160;
f[2816] = 36741600;
f[2817] = 36750000;
f[2818] = 36756909;
f[2819] = 36864000;
f[2820] = 36879360;
f[2821] = 36905625;
f[2822] = 37044000;
f[2823] = 37059435;
f[2824] = 37158912;
f[2825] = 37200870;
f[2826] = 37209375;
f[2827] = 37324800;
f[2828] = 37340352;
f[2829] = 37500000;
f[2830] = 37507050;
f[2831] = 37515625;
f[2832] = 37632000;
f[2833] = 37647680;
f[2834] = 37748736;
f[2835] = 37791360;
f[2836] = 37800000;
f[2837] = 37815750;
f[2838] = 37933056;
f[2839] = 37968750;
f[2840] = 38102400;
f[2841] = 38118276;
f[2842] = 38263752;
f[2843] = 38272500;
f[2844] = 38281250;
f[2845] = 38400000;
f[2846] = 38416000;
f[2847] = 38535168;
f[2848] = 38578680;
f[2849] = 38587500;
f[2850] = 38707200;
f[2851] = 38723328;
f[2852] = 38880000;
f[2853] = 38896200;
f[2854] = 39062500;
f[2855] = 39191040;
f[2856] = 39200000;
f[2857] = 39321600;
f[2858] = 39337984;
f[2859] = 39366000;
f[2860] = 39375000;
f[2861] = 39513600;
f[2862] = 39530064;
f[2863] = 39680928;
f[2864] = 39690000;
f[2865] = 39813120;
f[2866] = 39858075;
f[2867] = 40000000;
f[2868] = 40007520;
f[2869] = 40140800;
f[2870] = 40186125;
f[2871] = 40310784;
f[2872] = 40320000;
f[2873] = 40336800;
f[2874] = 40353607;
f[2875] = 40500000;
f[2876] = 40507614;
f[2877] = 40516875;
f[2878] = 40642560;
f[2879] = 40824000;
f[2880] = 40841010;
f[2881] = 40960000;
f[2882] = 41006250;
f[2883] = 41015625;
f[2884] = 41150592;
f[2885] = 41160000;
f[2886] = 41177150;
f[2887] = 41287680;
f[2888] = 41334300;
f[2889] = 41343750;
f[2890] = 41472000;
f[2891] = 41489280;
f[2892] = 41674500;
f[2893] = 41803776;
f[2894] = 41943040;
f[2895] = 41990400;
f[2896] = 42000000;
f[2897] = 42007896;
f[2898] = 42017500;
f[2899] = 42147840;
f[2900] = 42187500;
f[2901] = 42336000;
f[2902] = 42353640;
f[2903] = 42467328;
f[2904] = 42515280;
f[2905] = 42525000;
f[2906] = 42674688;
f[2907] = 42865200;
f[2908] = 42875000;
f[2909] = 43008000;
f[2910] = 43025920;
f[2911] = 43046721;
f[2912] = 43200000;
f[2913] = 43218000;
f[2914] = 43352064;
f[2915] = 43401015;
f[2916] = 43545600;
f[2917] = 43563744;
f[2918] = 43740000;
f[2919] = 43750000;
f[2920] = 43758225;
f[2921] = 43904000;
f[2922] = 44040192;
f[2923] = 44089920;
f[2924] = 44100000;
f[2925] = 44118375;
f[2926] = 44236800;
f[2927] = 44255232;
f[2928] = 44286750;
f[2929] = 44296875;
f[2930] = 44452800;
f[2931] = 44471322;
f[2932] = 44641044;
f[2933] = 44651250;
f[2934] = 44789760;
f[2935] = 44800000;
f[2936] = 44957696;
f[2937] = 45000000;
f[2938] = 45008460;
f[2939] = 45018750;
f[2940] = 45158400;
f[2941] = 45177216;
f[2942] = 45349632;
f[2943] = 45360000;
f[2944] = 45378900;
f[2945] = 45562500;
f[2946] = 45722880;
f[2947] = 45875200;
f[2948] = 45927000;
f[2949] = 45937500;
f[2950] = 46080000;
f[2951] = 46099200;
f[2952] = 46118408;
f[2953] = 46294416;
f[2954] = 46305000;
f[2955] = 46448640;
f[2956] = 46656000;
f[2957] = 46675440;
f[2958] = 46875000;
f[2959] = 47029248;
f[2960] = 47040000;
f[2961] = 47059600;
f[2962] = 47185920;
f[2963] = 47239200;
f[2964] = 47250000;
f[2965] = 47258883;
f[2966] = 47416320;
f[2967] = 47628000;
f[2968] = 47647845;
f[2969] = 47775744;
f[2970] = 47829690;
f[2971] = 47840625;
f[2972] = 48000000;
f[2973] = 48009024;
f[2974] = 48020000;
f[2975] = 48168960;
f[2976] = 48223350;
f[2977] = 48234375;
f[2978] = 48384000;
f[2979] = 48404160;
f[2980] = 48600000;
f[2981] = 48620250;
f[2982] = 48771072;
f[2983] = 48828125;
f[2984] = 48988800;
f[2985] = 49000000;
f[2986] = 49009212;
f[2987] = 49152000;
f[2988] = 49172480;
f[2989] = 49207500;
f[2990] = 49218750;
f[2991] = 49392000;
f[2992] = 49412580;
f[2993] = 49545216;
f[2994] = 49601160;
f[2995] = 49612500;
f[2996] = 49766400;
f[2997] = 49787136;
f[2998] = 50000000;
f[2999] = 50009400;
f[3000] = 50176000;
f[3001] = 50331648;
f[3002] = 50388480;
f[3003] = 50400000;
f[3004] = 50421000;
f[3005] = 50577408;
f[3006] = 50625000;
f[3007] = 50803200;
f[3008] = 50824368;
f[3009] = 51018336;
f[3010] = 51030000;
f[3011] = 51200000;
f[3012] = 51380224;
f[3013] = 51438240;
f[3014] = 51450000;
f[3015] = 51609600;
f[3016] = 51631104;
f[3017] = 51667875;
f[3018] = 51840000;
f[3019] = 51861600;
f[3020] = 51883209;
f[3021] = 52081218;
f[3022] = 52093125;
f[3023] = 52254720;
f[3024] = 52428800;
f[3025] = 52488000;
f[3026] = 52500000;
f[3027] = 52509870;
f[3028] = 52521875;
f[3029] = 52684800;
f[3030] = 52706752;
f[3031] = 52734375;
f[3032] = 52907904;
f[3033] = 52920000;
f[3034] = 52942050;
f[3035] = 53084160;
f[3036] = 53144100;
f[3037] = 53156250;
f[3038] = 53343360;
f[3039] = 53581500;
f[3040] = 53593750;
f[3041] = 53747712;
f[3042] = 53760000;
f[3043] = 53782400;
f[3044] = 54000000;
f[3045] = 54010152;
f[3046] = 54022500;
f[3047] = 54190080;
f[3048] = 54432000;
f[3049] = 54454680;
f[3050] = 54675000;
f[3051] = 54687500;
f[3052] = 54867456;
f[3053] = 54880000;
f[3054] = 55050240;
f[3055] = 55112400;
f[3056] = 55125000;
f[3057] = 55296000;
f[3058] = 55319040;
f[3059] = 55566000;
f[3060] = 55738368;
f[3061] = 55801305;
f[3062] = 55987200;
f[3063] = 56000000;
f[3064] = 56010528;
f[3065] = 56197120;
f[3066] = 56250000;
f[3067] = 56260575;
f[3068] = 56448000;
f[3069] = 56471520;
f[3070] = 56623104;
f[3071] = 56687040;
f[3072] = 56700000;
f[3073] = 56723625;
f[3074] = 56899584;
f[3075] = 56953125;
f[3076] = 57153600;
f[3077] = 57177414;
f[3078] = 57344000;
f[3079] = 57395628;
f[3080] = 57408750;
f[3081] = 57421875;
f[3082] = 57600000;
f[3083] = 57624000;
f[3084] = 57648010;
f[3085] = 57802752;
f[3086] = 57868020;
f[3087] = 57881250;
f[3088] = 58060800;
f[3089] = 58084992;
f[3090] = 58320000;
f[3091] = 58344300;
f[3092] = 58593750;
f[3093] = 58720256;
f[3094] = 58786560;
f[3095] = 58800000;
f[3096] = 58824500;
f[3097] = 58982400;
f[3098] = 59006976;
f[3099] = 59049000;
f[3100] = 59062500;
f[3101] = 59270400;
f[3102] = 59295096;
f[3103] = 59521392;
f[3104] = 59535000;
f[3105] = 59719680;
f[3106] = 60000000;
f[3107] = 60011280;
f[3108] = 60025000;
f[3109] = 60211200;
f[3110] = 60236288;
f[3111] = 60466176;
f[3112] = 60480000;
f[3113] = 60505200;
f[3114] = 60750000;
f[3115] = 60761421;
f[3116] = 60963840;
f[3117] = 61236000;
f[3118] = 61250000;
f[3119] = 61261515;
f[3120] = 61440000;
f[3121] = 61465600;
f[3122] = 61509375;
f[3123] = 61725888;
f[3124] = 61740000;
f[3125] = 61765725;
f[3126] = 61931520;
f[3127] = 62001450;
f[3128] = 62015625;
f[3129] = 62208000;
f[3130] = 62233920;
f[3131] = 62500000;
f[3132] = 62511750;
f[3133] = 62705664;
f[3134] = 62720000;
f[3135] = 62914560;
f[3136] = 62985600;
f[3137] = 63000000;
f[3138] = 63011844;
f[3139] = 63026250;
f[3140] = 63221760;
f[3141] = 63281250;
f[3142] = 63504000;
f[3143] = 63530460;
f[3144] = 63700992;
f[3145] = 63772920;
f[3146] = 63787500;
f[3147] = 64000000;
f[3148] = 64012032;
f[3149] = 64225280;
f[3150] = 64297800;
f[3151] = 64312500;
f[3152] = 64512000;
f[3153] = 64538880;
f[3154] = 64800000;
f[3155] = 64827000;
f[3156] = 65028096;
f[3157] = 65318400;
f[3158] = 65345616;
f[3159] = 65536000;
f[3160] = 65610000;
f[3161] = 65625000;
f[3162] = 65856000;
f[3163] = 65883440;
f[3164] = 66060288;
f[3165] = 66134880;
f[3166] = 66150000;
f[3167] = 66355200;
f[3168] = 66382848;
f[3169] = 66430125;
f[3170] = 66679200;
f[3171] = 66706983;
f[3172] = 66961566;
f[3173] = 66976875;
f[3174] = 67108864;
f[3175] = 67184640;
f[3176] = 67200000;
f[3177] = 67228000;
f[3178] = 67436544;
f[3179] = 67500000;
f[3180] = 67512690;
f[3181] = 67528125;
f[3182] = 67737600;
f[3183] = 67765824;
f[3184] = 68024448;
f[3185] = 68040000;
f[3186] = 68068350;
f[3187] = 68343750;
f[3188] = 68359375;
f[3189] = 68584320;
f[3190] = 68600000;
f[3191] = 68812800;
f[3192] = 68841472;
f[3193] = 68890500;
f[3194] = 68906250;
f[3195] = 69120000;
f[3196] = 69148800;
f[3197] = 69177612;
f[3198] = 69441624;
f[3199] = 69457500;
f[3200] = 69672960;
f[3201] = 69984000;
f[3202] = 70000000;
f[3203] = 70013160;
f[3204] = 70246400;
f[3205] = 70312500;
f[3206] = 70543872;
f[3207] = 70560000;
f[3208] = 70589400;
f[3209] = 70778880;
f[3210] = 70858800;
f[3211] = 70875000;
f[3212] = 71124480;
f[3213] = 71442000;
f[3214] = 71663616;
f[3215] = 71680000;
f[3216] = 71744535;
f[3217] = 72000000;
f[3218] = 72013536;
f[3219] = 72030000;
f[3220] = 72253440;
f[3221] = 72335025;
f[3222] = 72576000;
f[3223] = 72606240;
f[3224] = 72900000;
f[3225] = 72930375;
f[3226] = 73156608;
f[3227] = 73400320;
f[3228] = 73483200;
f[3229] = 73500000;
f[3230] = 73513818;
f[3231] = 73530625;
f[3232] = 73728000;
f[3233] = 73758720;
f[3234] = 73811250;
f[3235] = 73828125;
f[3236] = 74088000;
f[3237] = 74118870;
f[3238] = 74317824;
f[3239] = 74401740;
f[3240] = 74418750;
f[3241] = 74649600;
f[3242] = 74680704;
f[3243] = 75000000;
f[3244] = 75014100;
f[3245] = 75031250;
f[3246] = 75264000;
f[3247] = 75295360;
f[3248] = 75497472;
f[3249] = 75582720;
f[3250] = 75600000;
f[3251] = 75631500;
f[3252] = 75866112;
f[3253] = 75937500;
f[3254] = 76204800;
f[3255] = 76236552;
f[3256] = 76527504;
f[3257] = 76545000;
f[3258] = 76562500;
f[3259] = 76800000;
f[3260] = 76832000;
f[3261] = 77070336;
f[3262] = 77157360;
f[3263] = 77175000;
f[3264] = 77414400;
f[3265] = 77446656;
f[3266] = 77760000;
f[3267] = 77792400;
f[3268] = 78121827;
f[3269] = 78125000;
f[3270] = 78382080;
f[3271] = 78400000;
f[3272] = 78643200;
f[3273] = 78675968;
f[3274] = 78732000;
f[3275] = 78750000;
f[3276] = 78764805;
f[3277] = 79027200;
f[3278] = 79060128;
f[3279] = 79361856;
f[3280] = 79380000;
f[3281] = 79413075;
f[3282] = 79626240;
f[3283] = 79716150;
f[3284] = 79734375;
f[3285] = 80000000;
f[3286] = 80015040;
f[3287] = 80281600;
f[3288] = 80372250;
f[3289] = 80390625;
f[3290] = 80621568;
f[3291] = 80640000;
f[3292] = 80673600;
f[3293] = 80707214;
f[3294] = 81000000;
f[3295] = 81015228;
f[3296] = 81033750;
f[3297] = 81285120;
f[3298] = 81648000;
f[3299] = 81682020;
f[3300] = 81920000;
f[3301] = 82012500;
f[3302] = 82031250;
f[3303] = 82301184;
f[3304] = 82320000;
f[3305] = 82354300;
f[3306] = 82575360;
f[3307] = 82668600;
f[3308] = 82687500;
f[3309] = 82944000;
f[3310] = 82978560;
f[3311] = 83349000;
f[3312] = 83607552;
f[3313] = 83886080;
f[3314] = 83980800;
f[3315] = 84000000;
f[3316] = 84015792;
f[3317] = 84035000;
f[3318] = 84295680;
f[3319] = 84375000;
f[3320] = 84672000;
f[3321] = 84707280;
f[3322] = 84934656;
f[3323] = 85030560;
f[3324] = 85050000;
f[3325] = 85349376;
f[3326] = 85730400;
f[3327] = 85750000;
f[3328] = 85766121;
f[3329] = 86016000;
f[3330] = 86051840;
f[3331] = 86093442;
f[3332] = 86113125;
f[3333] = 86400000;
f[3334] = 86436000;
f[3335] = 86472015;
f[3336] = 86704128;
f[3337] = 86802030;
f[3338] = 86821875;
f[3339] = 87091200;
f[3340] = 87127488;
f[3341] = 87480000;
f[3342] = 87500000;
f[3343] = 87516450;
f[3344] = 87808000;
f[3345] = 87890625;
f[3346] = 88080384;
f[3347] = 88179840;
f[3348] = 88200000;
f[3349] = 88236750;
f[3350] = 88473600;
f[3351] = 88510464;
f[3352] = 88573500;
f[3353] = 88593750;
f[3354] = 88905600;
f[3355] = 88942644;
f[3356] = 89282088;
f[3357] = 89302500;
f[3358] = 89579520;
f[3359] = 89600000;
f[3360] = 89915392;
f[3361] = 90000000;
f[3362] = 90016920;
f[3363] = 90037500;
f[3364] = 90316800;
f[3365] = 90354432;
f[3366] = 90699264;
f[3367] = 90720000;
f[3368] = 90757800;
f[3369] = 91125000;
f[3370] = 91445760;
f[3371] = 91750400;
f[3372] = 91854000;
f[3373] = 91875000;
f[3374] = 92160000;
f[3375] = 92198400;
f[3376] = 92236816;
f[3377] = 92588832;
f[3378] = 92610000;
f[3379] = 92897280;
f[3380] = 93002175;
f[3381] = 93312000;
f[3382] = 93350880;
f[3383] = 93750000;
f[3384] = 93767625;
f[3385] = 94058496;
f[3386] = 94080000;
f[3387] = 94119200;
f[3388] = 94371840;
f[3389] = 94478400;
f[3390] = 94500000;
f[3391] = 94517766;
f[3392] = 94539375;
f[3393] = 94832640;
f[3394] = 94921875;
f[3395] = 95256000;
f[3396] = 95295690;
f[3397] = 95551488;
f[3398] = 95659380;
f[3399] = 95681250;
f[3400] = 95703125;
f[3401] = 96000000;
f[3402] = 96018048;
f[3403] = 96040000;
f[3404] = 96337920;
f[3405] = 96446700;
f[3406] = 96468750;
f[3407] = 96768000;
f[3408] = 96808320;
f[3409] = 97200000;
f[3410] = 97240500;
f[3411] = 97542144;
f[3412] = 97656250;
f[3413] = 97977600;
f[3414] = 98000000;
f[3415] = 98018424;
f[3416] = 98304000;
f[3417] = 98344960;
f[3418] = 98415000;
f[3419] = 98437500;
f[3420] = 98784000;
f[3421] = 98825160;
f[3422] = 99090432;
f[3423] = 99202320;
f[3424] = 99225000;
f[3425] = 99532800;
f[3426] = 99574272;
f[3427] = 100000000;
f[3428] = 100018800;
f[3429] = 100352000;
f[3430] = 100442349;
f[3431] = 100663296;
f[3432] = 100776960;
f[3433] = 100800000;
f[3434] = 100842000;
f[3435] = 101154816;
f[3436] = 101250000;
f[3437] = 101269035;
f[3438] = 101606400;
f[3439] = 101648736;
f[3440] = 102036672;
f[3441] = 102060000;
f[3442] = 102102525;
f[3443] = 102400000;
f[3444] = 102515625;
f[3445] = 102760448;
f[3446] = 102876480;
f[3447] = 102900000;
f[3448] = 102942875;
f[3449] = 103219200;
f[3450] = 103262208;
f[3451] = 103335750;
f[3452] = 103359375;
f[3453] = 103680000;
f[3454] = 103723200;
f[3455] = 103766418;
f[3456] = 104162436;
f[3457] = 104186250;
f[3458] = 104509440;
f[3459] = 104857600;
f[3460] = 104976000;
f[3461] = 105000000;
f[3462] = 105019740;
f[3463] = 105043750;
f[3464] = 105369600;
f[3465] = 105413504;
f[3466] = 105468750;
f[3467] = 105815808;
f[3468] = 105840000;
f[3469] = 105884100;
f[3470] = 106168320;
f[3471] = 106288200;
f[3472] = 106312500;
f[3473] = 106686720;
f[3474] = 107163000;
f[3475] = 107187500;
f[3476] = 107495424;
f[3477] = 107520000;
f[3478] = 107564800;
f[3479] = 108000000;
f[3480] = 108020304;
f[3481] = 108045000;
f[3482] = 108380160;
f[3483] = 108864000;
f[3484] = 108909360;
f[3485] = 109350000;
f[3486] = 109375000;
f[3487] = 109734912;
f[3488] = 109760000;
f[3489] = 110100480;
f[3490] = 110224800;
f[3491] = 110250000;
f[3492] = 110270727;
f[3493] = 110592000;
f[3494] = 110638080;
f[3495] = 110716875;
f[3496] = 111132000;
f[3497] = 111178305;
f[3498] = 111476736;
f[3499] = 111602610;
f[3500] = 111628125;
f[3501] = 111974400;
f[3502] = 112000000;
f[3503] = 112021056;
f[3504] = 112394240;
f[3505] = 112500000;
f[3506] = 112521150;
f[3507] = 112546875;
f[3508] = 112896000;
f[3509] = 112943040;
f[3510] = 113246208;
f[3511] = 113374080;
f[3512] = 113400000;
f[3513] = 113447250;
f[3514] = 113799168;
f[3515] = 113906250;
f[3516] = 114307200;
f[3517] = 114354828;
f[3518] = 114688000;
f[3519] = 114791256;
f[3520] = 114817500;
f[3521] = 114843750;
f[3522] = 115200000;
f[3523] = 115248000;
f[3524] = 115296020;
f[3525] = 115605504;
f[3526] = 115736040;
f[3527] = 115762500;
f[3528] = 116121600;
f[3529] = 116169984;
f[3530] = 116640000;
f[3531] = 116688600;
f[3532] = 117187500;
f[3533] = 117440512;
f[3534] = 117573120;
f[3535] = 117600000;
f[3536] = 117649000;
f[3537] = 117964800;
f[3538] = 118013952;
f[3539] = 118098000;
f[3540] = 118125000;
f[3541] = 118540800;
f[3542] = 118590192;
f[3543] = 119042784;
f[3544] = 119070000;
f[3545] = 119439360;
f[3546] = 119574225;
f[3547] = 120000000;
f[3548] = 120022560;
f[3549] = 120050000;
f[3550] = 120422400;
f[3551] = 120472576;
f[3552] = 120558375;
f[3553] = 120932352;
f[3554] = 120960000;
f[3555] = 121010400;
f[3556] = 121060821;
f[3557] = 121500000;
f[3558] = 121522842;
f[3559] = 121550625;
f[3560] = 121927680;
f[3561] = 122472000;
f[3562] = 122500000;
f[3563] = 122523030;
f[3564] = 122880000;
f[3565] = 122931200;
f[3566] = 123018750;
f[3567] = 123046875;
f[3568] = 123451776;
f[3569] = 123480000;
f[3570] = 123531450;
f[3571] = 123863040;
f[3572] = 124002900;
f[3573] = 124031250;
f[3574] = 124416000;
f[3575] = 124467840;
f[3576] = 125000000;
f[3577] = 125023500;
f[3578] = 125411328;
f[3579] = 125440000;
f[3580] = 125829120;
f[3581] = 125971200;
f[3582] = 126000000;
f[3583] = 126023688;
f[3584] = 126052500;
f[3585] = 126443520;
f[3586] = 126562500;
f[3587] = 127008000;
f[3588] = 127060920;
f[3589] = 127401984;
f[3590] = 127545840;
f[3591] = 127575000;
f[3592] = 128000000;
f[3593] = 128024064;
f[3594] = 128450560;
f[3595] = 128595600;
f[3596] = 128625000;
f[3597] = 129024000;
f[3598] = 129077760;
f[3599] = 129140163;
f[3600] = 129600000;
f[3601] = 129654000;
f[3602] = 130056192;
f[3603] = 130203045;
f[3604] = 130636800;
f[3605] = 130691232;
f[3606] = 131072000;
f[3607] = 131220000;
f[3608] = 131250000;
f[3609] = 131274675;
f[3610] = 131712000;
f[3611] = 131766880;
f[3612] = 132120576;
f[3613] = 132269760;
f[3614] = 132300000;
f[3615] = 132355125;
f[3616] = 132710400;
f[3617] = 132765696;
f[3618] = 132860250;
f[3619] = 132890625;
f[3620] = 133358400;
f[3621] = 133413966;
f[3622] = 133923132;
f[3623] = 133953750;
f[3624] = 133984375;
f[3625] = 134217728;
f[3626] = 134369280;
f[3627] = 134400000;
f[3628] = 134456000;
f[3629] = 134873088;
f[3630] = 135000000;
f[3631] = 135025380;
f[3632] = 135056250;
f[3633] = 135475200;
f[3634] = 135531648;
f[3635] = 136048896;
f[3636] = 136080000;
f[3637] = 136136700;
f[3638] = 136687500;
f[3639] = 136718750;
f[3640] = 137168640;
f[3641] = 137200000;
f[3642] = 137625600;
f[3643] = 137682944;
f[3644] = 137781000;
f[3645] = 137812500;
f[3646] = 138240000;
f[3647] = 138297600;
f[3648] = 138355224;
f[3649] = 138883248;
f[3650] = 138915000;
f[3651] = 139345920;
f[3652] = 139968000;
f[3653] = 140000000;
f[3654] = 140026320;
f[3655] = 140492800;
f[3656] = 140625000;
f[3657] = 141087744;
f[3658] = 141120000;
f[3659] = 141178800;
f[3660] = 141557760;
f[3661] = 141717600;
f[3662] = 141750000;
f[3663] = 141776649;
f[3664] = 142248960;
f[3665] = 142884000;
f[3666] = 142943535;
f[3667] = 143327232;
f[3668] = 143360000;
f[3669] = 143489070;
f[3670] = 143521875;
f[3671] = 144000000;
f[3672] = 144027072;
f[3673] = 144060000;
f[3674] = 144120025;
f[3675] = 144506880;
f[3676] = 144670050;
f[3677] = 144703125;
f[3678] = 145152000;
f[3679] = 145212480;
f[3680] = 145800000;
f[3681] = 145860750;
f[3682] = 146313216;
f[3683] = 146484375;
f[3684] = 146800640;
f[3685] = 146966400;
f[3686] = 147000000;
f[3687] = 147027636;
f[3688] = 147061250;
f[3689] = 147456000;
f[3690] = 147517440;
f[3691] = 147622500;
f[3692] = 147656250;
f[3693] = 148176000;
f[3694] = 148237740;
f[3695] = 148635648;
f[3696] = 148803480;
f[3697] = 148837500;
f[3698] = 149299200;
f[3699] = 149361408;
f[3700] = 150000000;
f[3701] = 150028200;
f[3702] = 150062500;
f[3703] = 150528000;
f[3704] = 150590720;
f[3705] = 150994944;
f[3706] = 151165440;
f[3707] = 151200000;
f[3708] = 151263000;
f[3709] = 151732224;
f[3710] = 151875000;
f[3711] = 152409600;
f[3712] = 152473104;
f[3713] = 153055008;
f[3714] = 153090000;
f[3715] = 153125000;
f[3716] = 153600000;
f[3717] = 153664000;
f[3718] = 154140672;
f[3719] = 154314720;
f[3720] = 154350000;
f[3721] = 154828800;
f[3722] = 154893312;
f[3723] = 155003625;
f[3724] = 155520000;
f[3725] = 155584800;
f[3726] = 155649627;
f[3727] = 156243654;
f[3728] = 156250000;
f[3729] = 156279375;
f[3730] = 156764160;
f[3731] = 156800000;
f[3732] = 157286400;
f[3733] = 157351936;
f[3734] = 157464000;
f[3735] = 157500000;
f[3736] = 157529610;
f[3737] = 157565625;
f[3738] = 158054400;
f[3739] = 158120256;
f[3740] = 158203125;
f[3741] = 158723712;
f[3742] = 158760000;
f[3743] = 158826150;
f[3744] = 159252480;
f[3745] = 159432300;
f[3746] = 159468750;
f[3747] = 160000000;
f[3748] = 160030080;
f[3749] = 160563200;
f[3750] = 160744500;
f[3751] = 160781250;
f[3752] = 161243136;
f[3753] = 161280000;
f[3754] = 161347200;
f[3755] = 161414428;
f[3756] = 162000000;
f[3757] = 162030456;
f[3758] = 162067500;
f[3759] = 162570240;
f[3760] = 163296000;
f[3761] = 163364040;
f[3762] = 163840000;
f[3763] = 164025000;
f[3764] = 164062500;
f[3765] = 164602368;
f[3766] = 164640000;
f[3767] = 164708600;
f[3768] = 165150720;
f[3769] = 165337200;
f[3770] = 165375000;
f[3771] = 165888000;
f[3772] = 165957120;
f[3773] = 166698000;
f[3774] = 167215104;
f[3775] = 167403915;
f[3776] = 167772160;
f[3777] = 167961600;
f[3778] = 168000000;
f[3779] = 168031584;
f[3780] = 168070000;
f[3781] = 168591360;
f[3782] = 168750000;
f[3783] = 168781725;
f[3784] = 169344000;
f[3785] = 169414560;
f[3786] = 169869312;
f[3787] = 170061120;
f[3788] = 170100000;
f[3789] = 170170875;
f[3790] = 170698752;
f[3791] = 170859375;
f[3792] = 171460800;
f[3793] = 171500000;
f[3794] = 171532242;
f[3795] = 172032000;
f[3796] = 172103680;
f[3797] = 172186884;
f[3798] = 172226250;
f[3799] = 172265625;
f[3800] = 172800000;
f[3801] = 172872000;
f[3802] = 172944030;
f[3803] = 173408256;
f[3804] = 173604060;
f[3805] = 173643750;
f[3806] = 174182400;
f[3807] = 174254976;
f[3808] = 174960000;
f[3809] = 175000000;
f[3810] = 175032900;
f[3811] = 175616000;
f[3812] = 175781250;
f[3813] = 176160768;
f[3814] = 176359680;
f[3815] = 176400000;
f[3816] = 176473500;
f[3817] = 176947200;
f[3818] = 177020928;
f[3819] = 177147000;
f[3820] = 177187500;
f[3821] = 177811200;
f[3822] = 177885288;
f[3823] = 178564176;
f[3824] = 178605000;
f[3825] = 179159040;
f[3826] = 179200000;
f[3827] = 179830784;
f[3828] = 180000000;
f[3829] = 180033840;
f[3830] = 180075000;
f[3831] = 180633600;
f[3832] = 180708864;
f[3833] = 181398528;
f[3834] = 181440000;
f[3835] = 181515600;
f[3836] = 182250000;
f[3837] = 182284263;
f[3838] = 182891520;
f[3839] = 183500800;
f[3840] = 183708000;
f[3841] = 183750000;
f[3842] = 183784545;
f[3843] = 184320000;
f[3844] = 184396800;
f[3845] = 184473632;
f[3846] = 184528125;
f[3847] = 185177664;
f[3848] = 185220000;
f[3849] = 185297175;
f[3850] = 185794560;
f[3851] = 186004350;
f[3852] = 186046875;
f[3853] = 186624000;
f[3854] = 186701760;
f[3855] = 187500000;
f[3856] = 187535250;
f[3857] = 187578125;
f[3858] = 188116992;
f[3859] = 188160000;
f[3860] = 188238400;
f[3861] = 188743680;
f[3862] = 188956800;
f[3863] = 189000000;
f[3864] = 189035532;
f[3865] = 189078750;
f[3866] = 189665280;
f[3867] = 189843750;
f[3868] = 190512000;
f[3869] = 190591380;
f[3870] = 191102976;
f[3871] = 191318760;
f[3872] = 191362500;
f[3873] = 191406250;
f[3874] = 192000000;
f[3875] = 192036096;
f[3876] = 192080000;
f[3877] = 192675840;
f[3878] = 192893400;
f[3879] = 192937500;
f[3880] = 193536000;
f[3881] = 193616640;
f[3882] = 194400000;
f[3883] = 194481000;
f[3884] = 195084288;
f[3885] = 195312500;
f[3886] = 195955200;
f[3887] = 196000000;
f[3888] = 196036848;
f[3889] = 196608000;
f[3890] = 196689920;
f[3891] = 196830000;
f[3892] = 196875000;
f[3893] = 197568000;
f[3894] = 197650320;
f[3895] = 198180864;
f[3896] = 198404640;
f[3897] = 198450000;
f[3898] = 199065600;
f[3899] = 199148544;
f[3900] = 199290375;
f[3901] = 200000000;
f[3902] = 200037600;
f[3903] = 200120949;
f[3904] = 200704000;
f[3905] = 200884698;
f[3906] = 200930625;
f[3907] = 201326592;
f[3908] = 201553920;
f[3909] = 201600000;
f[3910] = 201684000;
f[3911] = 201768035;
f[3912] = 202309632;
f[3913] = 202500000;
f[3914] = 202538070;
f[3915] = 202584375;
f[3916] = 203212800;
f[3917] = 203297472;
f[3918] = 204073344;
f[3919] = 204120000;
f[3920] = 204205050;
f[3921] = 204800000;
f[3922] = 205031250;
f[3923] = 205078125;
f[3924] = 205520896;
f[3925] = 205752960;
f[3926] = 205800000;
f[3927] = 205885750;
f[3928] = 206438400;
f[3929] = 206524416;
f[3930] = 206671500;
f[3931] = 206718750;
f[3932] = 207360000;
f[3933] = 207446400;
f[3934] = 207532836;
f[3935] = 208324872;
f[3936] = 208372500;
f[3937] = 209018880;
f[3938] = 209715200;
f[3939] = 209952000;
f[3940] = 210000000;
f[3941] = 210039480;
f[3942] = 210087500;
f[3943] = 210739200;
f[3944] = 210827008;
f[3945] = 210937500;
f[3946] = 211631616;
f[3947] = 211680000;
f[3948] = 211768200;
f[3949] = 212336640;
f[3950] = 212576400;
f[3951] = 212625000;
f[3952] = 213373440;
f[3953] = 214326000;
f[3954] = 214375000;
f[3955] = 214990848;
f[3956] = 215040000;
f[3957] = 215129600;
f[3958] = 215233605;
f[3959] = 216000000;
f[3960] = 216040608;
f[3961] = 216090000;
f[3962] = 216760320;
f[3963] = 217005075;
f[3964] = 217728000;
f[3965] = 217818720;
f[3966] = 218700000;
f[3967] = 218750000;
f[3968] = 218791125;
f[3969] = 219469824;
f[3970] = 219520000;
f[3971] = 220200960;
f[3972] = 220449600;
f[3973] = 220500000;
f[3974] = 220541454;
f[3975] = 220591875;
f[3976] = 221184000;
f[3977] = 221276160;
f[3978] = 221433750;
f[3979] = 221484375;
f[3980] = 222264000;
f[3981] = 222356610;
f[3982] = 222953472;
f[3983] = 223205220;
f[3984] = 223256250;
f[3985] = 223948800;
f[3986] = 224000000;
f[3987] = 224042112;
f[3988] = 224788480;
f[3989] = 225000000;
f[3990] = 225042300;
f[3991] = 225093750;
f[3992] = 225792000;
f[3993] = 225886080;
f[3994] = 226492416;
f[3995] = 226748160;
f[3996] = 226800000;
f[3997] = 226894500;
f[3998] = 227598336;
f[3999] = 227812500;
f[4000] = 228614400;
f[4001] = 228709656;
f[4002] = 229376000;
f[4003] = 229582512;
f[4004] = 229635000;
f[4005] = 229687500;
f[4006] = 230400000;
f[4007] = 230496000;
f[4008] = 230592040;
f[4009] = 231211008;
f[4010] = 231472080;
f[4011] = 231525000;
f[4012] = 232243200;
f[4013] = 232339968;
f[4014] = 233280000;
f[4015] = 233377200;
f[4016] = 234365481;
f[4017] = 234375000;
f[4018] = 234881024;
f[4019] = 235146240;
f[4020] = 235200000;
f[4021] = 235298000;
f[4022] = 235929600;
f[4023] = 236027904;
f[4024] = 236196000;
f[4025] = 236250000;
f[4026] = 236294415;
f[4027] = 237081600;
f[4028] = 237180384;
f[4029] = 238085568;
f[4030] = 238140000;
f[4031] = 238239225;
f[4032] = 238878720;
f[4033] = 239148450;
f[4034] = 239203125;
f[4035] = 240000000;
f[4036] = 240045120;
f[4037] = 240100000;
f[4038] = 240844800;
f[4039] = 240945152;
f[4040] = 241116750;
f[4041] = 241171875;
f[4042] = 241864704;
f[4043] = 241920000;
f[4044] = 242020800;
f[4045] = 242121642;
f[4046] = 243000000;
f[4047] = 243045684;
f[4048] = 243101250;
f[4049] = 243855360;
f[4050] = 244140625;
f[4051] = 244944000;
f[4052] = 245000000;
f[4053] = 245046060;
f[4054] = 245760000;
f[4055] = 245862400;
f[4056] = 246037500;
f[4057] = 246093750;
f[4058] = 246903552;
f[4059] = 246960000;
f[4060] = 247062900;
f[4061] = 247726080;
f[4062] = 248005800;
f[4063] = 248062500;
f[4064] = 248832000;
f[4065] = 248935680;
f[4066] = 250000000;
f[4067] = 250047000;
f[4068] = 250822656;
f[4069] = 250880000;
f[4070] = 251658240;
f[4071] = 251942400;
f[4072] = 252000000;
f[4073] = 252047376;
f[4074] = 252105000;
f[4075] = 252887040;
f[4076] = 253125000;
f[4077] = 254016000;
f[4078] = 254121840;
f[4079] = 254803968;
f[4080] = 255091680;
f[4081] = 255150000;
f[4082] = 256000000;
f[4083] = 256048128;
f[4084] = 256901120;
f[4085] = 257191200;
f[4086] = 257250000;
f[4087] = 257298363;
f[4088] = 258048000;
f[4089] = 258155520;
f[4090] = 258280326;
f[4091] = 258339375;
f[4092] = 259200000;
f[4093] = 259308000;
f[4094] = 259416045;
f[4095] = 260112384;
f[4096] = 260406090;
f[4097] = 260465625;
f[4098] = 261273600;
f[4099] = 261382464;
f[4100] = 262144000;
f[4101] = 262440000;
f[4102] = 262500000;
f[4103] = 262549350;
f[4104] = 262609375;
f[4105] = 263424000;
f[4106] = 263533760;
f[4107] = 263671875;
f[4108] = 264241152;
f[4109] = 264539520;
f[4110] = 264600000;
f[4111] = 264710250;
f[4112] = 265420800;
f[4113] = 265531392;
f[4114] = 265720500;
f[4115] = 265781250;
f[4116] = 266716800;
f[4117] = 266827932;
f[4118] = 267846264;
f[4119] = 267907500;
f[4120] = 267968750;
f[4121] = 268435456;
f[4122] = 268738560;
f[4123] = 268800000;
f[4124] = 268912000;
f[4125] = 269746176;
f[4126] = 270000000;
f[4127] = 270050760;
f[4128] = 270112500;
f[4129] = 270950400;
f[4130] = 271063296;
f[4131] = 272097792;
f[4132] = 272160000;
f[4133] = 272273400;
f[4134] = 273375000;
f[4135] = 273437500;
f[4136] = 274337280;
f[4137] = 274400000;
f[4138] = 275251200;
f[4139] = 275365888;
f[4140] = 275562000;
f[4141] = 275625000;
f[4142] = 276480000;
f[4143] = 276595200;
f[4144] = 276710448;
f[4145] = 277766496;
f[4146] = 277830000;
f[4147] = 278691840;
f[4148] = 279006525;
f[4149] = 279936000;
f[4150] = 280000000;
f[4151] = 280052640;
f[4152] = 280985600;
f[4153] = 281250000;
f[4154] = 281302875;
f[4155] = 282175488;
f[4156] = 282240000;
f[4157] = 282357600;
f[4158] = 282475249;
f[4159] = 283115520;
f[4160] = 283435200;
f[4161] = 283500000;
f[4162] = 283553298;
f[4163] = 283618125;
f[4164] = 284497920;
f[4165] = 284765625;
f[4166] = 285768000;
f[4167] = 285887070;
f[4168] = 286654464;
f[4169] = 286720000;
f[4170] = 286978140;
f[4171] = 287043750;
f[4172] = 287109375;
f[4173] = 288000000;
f[4174] = 288054144;
f[4175] = 288120000;
f[4176] = 288240050;
f[4177] = 289013760;
f[4178] = 289340100;
f[4179] = 289406250;
f[4180] = 290304000;
f[4181] = 290424960;
f[4182] = 291600000;
f[4183] = 291721500;
f[4184] = 292626432;
f[4185] = 292968750;
f[4186] = 293601280;
f[4187] = 293932800;
f[4188] = 294000000;
f[4189] = 294055272;
f[4190] = 294122500;
f[4191] = 294912000;
f[4192] = 295034880;
f[4193] = 295245000;
f[4194] = 295312500;
f[4195] = 296352000;
f[4196] = 296475480;
f[4197] = 297271296;
f[4198] = 297606960;
f[4199] = 297675000;
f[4200] = 298598400;
f[4201] = 298722816;
f[4202] = 300000000;
f[4203] = 300056400;
f[4204] = 300125000;
f[4205] = 301056000;
f[4206] = 301181440;
f[4207] = 301327047;
f[4208] = 301989888;
f[4209] = 302330880;
f[4210] = 302400000;
f[4211] = 302526000;
f[4212] = 303464448;
f[4213] = 303750000;
f[4214] = 303807105;
f[4215] = 304819200;
f[4216] = 304946208;
f[4217] = 306110016;
f[4218] = 306180000;
f[4219] = 306250000;
f[4220] = 306307575;
f[4221] = 307200000;
f[4222] = 307328000;
f[4223] = 307546875;
f[4224] = 308281344;
f[4225] = 308629440;
f[4226] = 308700000;
f[4227] = 308828625;
f[4228] = 309657600;
f[4229] = 309786624;
f[4230] = 310007250;
f[4231] = 310078125;
f[4232] = 311040000;
f[4233] = 311169600;
f[4234] = 311299254;
f[4235] = 312487308;
f[4236] = 312500000;
f[4237] = 312558750;
f[4238] = 313528320;
f[4239] = 313600000;
f[4240] = 314572800;
f[4241] = 314703872;
f[4242] = 314928000;
f[4243] = 315000000;
f[4244] = 315059220;
f[4245] = 315131250;
f[4246] = 316108800;
f[4247] = 316240512;
f[4248] = 316406250;
f[4249] = 317447424;
f[4250] = 317520000;
f[4251] = 317652300;
f[4252] = 318504960;
f[4253] = 318864600;
f[4254] = 318937500;
f[4255] = 320000000;
f[4256] = 320060160;
f[4257] = 321126400;
f[4258] = 321489000;
f[4259] = 321562500;
f[4260] = 322486272;
f[4261] = 322560000;
f[4262] = 322694400;
f[4263] = 322828856;
f[4264] = 324000000;
f[4265] = 324060912;
f[4266] = 324135000;
f[4267] = 325140480;
f[4268] = 326592000;
f[4269] = 326728080;
f[4270] = 327680000;
f[4271] = 328050000;
f[4272] = 328125000;
f[4273] = 329204736;
f[4274] = 329280000;
f[4275] = 329417200;
f[4276] = 330301440;
f[4277] = 330674400;
f[4278] = 330750000;
f[4279] = 330812181;
f[4280] = 331776000;
f[4281] = 331914240;
f[4282] = 332150625;
f[4283] = 333396000;
f[4284] = 333534915;
f[4285] = 334430208;
f[4286] = 334807830;
f[4287] = 334884375;
f[4288] = 335544320;
f[4289] = 335923200;
f[4290] = 336000000;
f[4291] = 336063168;
f[4292] = 336140000;
f[4293] = 337182720;
f[4294] = 337500000;
f[4295] = 337563450;
f[4296] = 337640625;
f[4297] = 338688000;
f[4298] = 338829120;
f[4299] = 339738624;
f[4300] = 340122240;
f[4301] = 340200000;
f[4302] = 340341750;
f[4303] = 341397504;
f[4304] = 341718750;
f[4305] = 341796875;
f[4306] = 342921600;
f[4307] = 343000000;
f[4308] = 343064484;
f[4309] = 344064000;
f[4310] = 344207360;
f[4311] = 344373768;
f[4312] = 344452500;
f[4313] = 344531250;
f[4314] = 345600000;
f[4315] = 345744000;
f[4316] = 345888060;
f[4317] = 346816512;
f[4318] = 347208120;
f[4319] = 347287500;
f[4320] = 348364800;
f[4321] = 348509952;
f[4322] = 349920000;
f[4323] = 350000000;
f[4324] = 350065800;
f[4325] = 351232000;
f[4326] = 351562500;
f[4327] = 352321536;
f[4328] = 352719360;
f[4329] = 352800000;
f[4330] = 352947000;
f[4331] = 353894400;
f[4332] = 354041856;
f[4333] = 354294000;
f[4334] = 354375000;
f[4335] = 355622400;
f[4336] = 355770576;
f[4337] = 357128352;
f[4338] = 357210000;
f[4339] = 358318080;
f[4340] = 358400000;
f[4341] = 358722675;
f[4342] = 359661568;
f[4343] = 360000000;
f[4344] = 360067680;
f[4345] = 360150000;
f[4346] = 361267200;
f[4347] = 361417728;
f[4348] = 361675125;
f[4349] = 362797056;
f[4350] = 362880000;
f[4351] = 363031200;
f[4352] = 363182463;
f[4353] = 364500000;
f[4354] = 364568526;
f[4355] = 364651875;
f[4356] = 365783040;
f[4357] = 367001600;
f[4358] = 367416000;
f[4359] = 367500000;
f[4360] = 367569090;
f[4361] = 367653125;
f[4362] = 368640000;
f[4363] = 368793600;
f[4364] = 368947264;
f[4365] = 369056250;
f[4366] = 369140625;
f[4367] = 370355328;
f[4368] = 370440000;
f[4369] = 370594350;
f[4370] = 371589120;
f[4371] = 372008700;
f[4372] = 372093750;
f[4373] = 373248000;
f[4374] = 373403520;
f[4375] = 375000000;
f[4376] = 375070500;
f[4377] = 375156250;
f[4378] = 376233984;
f[4379] = 376320000;
f[4380] = 376476800;
f[4381] = 377487360;
f[4382] = 377913600;
f[4383] = 378000000;
f[4384] = 378071064;
f[4385] = 378157500;
f[4386] = 379330560;
f[4387] = 379687500;
f[4388] = 381024000;
f[4389] = 381182760;
f[4390] = 382205952;
f[4391] = 382637520;
f[4392] = 382725000;
f[4393] = 382812500;
f[4394] = 384000000;
f[4395] = 384072192;
f[4396] = 384160000;
f[4397] = 385351680;
f[4398] = 385786800;
f[4399] = 385875000;
f[4400] = 387072000;
f[4401] = 387233280;
f[4402] = 387420489;
f[4403] = 388800000;
f[4404] = 388962000;
f[4405] = 390168576;
f[4406] = 390609135;
f[4407] = 390625000;
f[4408] = 391910400;
f[4409] = 392000000;
f[4410] = 392073696;
f[4411] = 393216000;
f[4412] = 393379840;
f[4413] = 393660000;
f[4414] = 393750000;
f[4415] = 393824025;
f[4416] = 395136000;
f[4417] = 395300640;
f[4418] = 396361728;
f[4419] = 396809280;
f[4420] = 396900000;
f[4421] = 397065375;
f[4422] = 398131200;
f[4423] = 398297088;
f[4424] = 398580750;
f[4425] = 398671875;
f[4426] = 400000000;
f[4427] = 400075200;
f[4428] = 400241898;
f[4429] = 401408000;
f[4430] = 401769396;
f[4431] = 401861250;
f[4432] = 401953125;
f[4433] = 402653184;
f[4434] = 403107840;
f[4435] = 403200000;
f[4436] = 403368000;
f[4437] = 403536070;
f[4438] = 404619264;
f[4439] = 405000000;
f[4440] = 405076140;
f[4441] = 405168750;
f[4442] = 406425600;
f[4443] = 406594944;
f[4444] = 408146688;
f[4445] = 408240000;
f[4446] = 408410100;
f[4447] = 409600000;
f[4448] = 410062500;
f[4449] = 410156250;
f[4450] = 411041792;
f[4451] = 411505920;
f[4452] = 411600000;
f[4453] = 411771500;
f[4454] = 412876800;
f[4455] = 413048832;
f[4456] = 413343000;
f[4457] = 413437500;
f[4458] = 414720000;
f[4459] = 414892800;
f[4460] = 415065672;
f[4461] = 416649744;
f[4462] = 416745000;
f[4463] = 418037760;
f[4464] = 419430400;
f[4465] = 419904000;
f[4466] = 420000000;
f[4467] = 420078960;
f[4468] = 420175000;
f[4469] = 421478400;
f[4470] = 421654016;
f[4471] = 421875000;
f[4472] = 423263232;
f[4473] = 423360000;
f[4474] = 423536400;
f[4475] = 424673280;
f[4476] = 425152800;
f[4477] = 425250000;
f[4478] = 425329947;
f[4479] = 426746880;
f[4480] = 428652000;
f[4481] = 428750000;
f[4482] = 428830605;
f[4483] = 429981696;
f[4484] = 430080000;
f[4485] = 430259200;
f[4486] = 430467210;
f[4487] = 430565625;
f[4488] = 432000000;
f[4489] = 432081216;
f[4490] = 432180000;
f[4491] = 432360075;
f[4492] = 433520640;
f[4493] = 434010150;
f[4494] = 434109375;
f[4495] = 435456000;
f[4496] = 435637440;
f[4497] = 437400000;
f[4498] = 437500000;
f[4499] = 437582250;
f[4500] = 438939648;
f[4501] = 439040000;
f[4502] = 439453125;
f[4503] = 440401920;
f[4504] = 440899200;
f[4505] = 441000000;
f[4506] = 441082908;
f[4507] = 441183750;
f[4508] = 442368000;
f[4509] = 442552320;
f[4510] = 442867500;
f[4511] = 442968750;
f[4512] = 444528000;
f[4513] = 444713220;
f[4514] = 445906944;
f[4515] = 446410440;
f[4516] = 446512500;
f[4517] = 447897600;
f[4518] = 448000000;
f[4519] = 448084224;
f[4520] = 449576960;
f[4521] = 450000000;
f[4522] = 450084600;
f[4523] = 450187500;
f[4524] = 451584000;
f[4525] = 451772160;
f[4526] = 452984832;
f[4527] = 453496320;
f[4528] = 453600000;
f[4529] = 453789000;
f[4530] = 455196672;
f[4531] = 455625000;
f[4532] = 457228800;
f[4533] = 457419312;
f[4534] = 458752000;
f[4535] = 459165024;
f[4536] = 459270000;
f[4537] = 459375000;
f[4538] = 460800000;
f[4539] = 460992000;
f[4540] = 461184080;
f[4541] = 462422016;
f[4542] = 462944160;
f[4543] = 463050000;
f[4544] = 464486400;
f[4545] = 464679936;
f[4546] = 465010875;
f[4547] = 466560000;
f[4548] = 466754400;
f[4549] = 466948881;
f[4550] = 468730962;
f[4551] = 468750000;
f[4552] = 468838125;
f[4553] = 469762048;
f[4554] = 470292480;
f[4555] = 470400000;
f[4556] = 470596000;
f[4557] = 471859200;
f[4558] = 472055808;
f[4559] = 472392000;
f[4560] = 472500000;
f[4561] = 472588830;
f[4562] = 472696875;
f[4563] = 474163200;
f[4564] = 474360768;
f[4565] = 474609375;
f[4566] = 476171136;
f[4567] = 476280000;
f[4568] = 476478450;
f[4569] = 477757440;
f[4570] = 478296900;
f[4571] = 478406250;
f[4572] = 478515625;
f[4573] = 480000000;
f[4574] = 480090240;
f[4575] = 480200000;
f[4576] = 481689600;
f[4577] = 481890304;
f[4578] = 482233500;
f[4579] = 482343750;
f[4580] = 483729408;
f[4581] = 483840000;
f[4582] = 484041600;
f[4583] = 484243284;
f[4584] = 486000000;
f[4585] = 486091368;
f[4586] = 486202500;
f[4587] = 487710720;
f[4588] = 488281250;
f[4589] = 489888000;
f[4590] = 490000000;
f[4591] = 490092120;
f[4592] = 491520000;
f[4593] = 491724800;
f[4594] = 492075000;
f[4595] = 492187500;
f[4596] = 493807104;
f[4597] = 493920000;
f[4598] = 494125800;
f[4599] = 495452160;
f[4600] = 496011600;
f[4601] = 496125000;
f[4602] = 497664000;
f[4603] = 497871360;
f[4604] = 500000000;
f[4605] = 500094000;
f[4606] = 501645312;
f[4607] = 501760000;
f[4608] = 502211745;
f[4609] = 503316480;
f[4610] = 503884800;
f[4611] = 504000000;
f[4612] = 504094752;
f[4613] = 504210000;
f[4614] = 505774080;
f[4615] = 506250000;
f[4616] = 506345175;
f[4617] = 508032000;
f[4618] = 508243680;
f[4619] = 509607936;
f[4620] = 510183360;
f[4621] = 510300000;
f[4622] = 510512625;
f[4623] = 512000000;
f[4624] = 512096256;
f[4625] = 512578125;
f[4626] = 513802240;
f[4627] = 514382400;
f[4628] = 514500000;
f[4629] = 514596726;
f[4630] = 514714375;
f[4631] = 516096000;
f[4632] = 516311040;
f[4633] = 516560652;
f[4634] = 516678750;
f[4635] = 516796875;
f[4636] = 518400000;
f[4637] = 518616000;
f[4638] = 518832090;
f[4639] = 520224768;
f[4640] = 520812180;
f[4641] = 520931250;
f[4642] = 522547200;
f[4643] = 522764928;
f[4644] = 524288000;
f[4645] = 524880000;
f[4646] = 525000000;
f[4647] = 525098700;
f[4648] = 525218750;
f[4649] = 526848000;
f[4650] = 527067520;
f[4651] = 527343750;
f[4652] = 528482304;
f[4653] = 529079040;
f[4654] = 529200000;
f[4655] = 529420500;
f[4656] = 530841600;
f[4657] = 531062784;
f[4658] = 531441000;
f[4659] = 531562500;
f[4660] = 533433600;
f[4661] = 533655864;
f[4662] = 535692528;
f[4663] = 535815000;
f[4664] = 535937500;
f[4665] = 536870912;
f[4666] = 537477120;
f[4667] = 537600000;
f[4668] = 537824000;
f[4669] = 539492352;
f[4670] = 540000000;
f[4671] = 540101520;
f[4672] = 540225000;
f[4673] = 541900800;
f[4674] = 542126592;
f[4675] = 544195584;
f[4676] = 544320000;
f[4677] = 544546800;
f[4678] = 546750000;
f[4679] = 546852789;
f[4680] = 546875000;
f[4681] = 548674560;
f[4682] = 548800000;
f[4683] = 550502400;
f[4684] = 550731776;
f[4685] = 551124000;
f[4686] = 551250000;
f[4687] = 551353635;
f[4688] = 552960000;
f[4689] = 553190400;
f[4690] = 553420896;
f[4691] = 553584375;
f[4692] = 555532992;
f[4693] = 555660000;
f[4694] = 555891525;
f[4695] = 557383680;
f[4696] = 558013050;
f[4697] = 558140625;
f[4698] = 559872000;
f[4699] = 560000000;
f[4700] = 560105280;
f[4701] = 561971200;
f[4702] = 562500000;
f[4703] = 562605750;
f[4704] = 562734375;
f[4705] = 564350976;
f[4706] = 564480000;
f[4707] = 564715200;
f[4708] = 564950498;
f[4709] = 566231040;
f[4710] = 566870400;
f[4711] = 567000000;
f[4712] = 567106596;
f[4713] = 567236250;
f[4714] = 568995840;
f[4715] = 569531250;
f[4716] = 571536000;
f[4717] = 571774140;
f[4718] = 573308928;
f[4719] = 573440000;
f[4720] = 573956280;
f[4721] = 574087500;
f[4722] = 574218750;
f[4723] = 576000000;
f[4724] = 576108288;
f[4725] = 576240000;
f[4726] = 576480100;
f[4727] = 578027520;
f[4728] = 578680200;
f[4729] = 578812500;
f[4730] = 580608000;
f[4731] = 580849920;
f[4732] = 583200000;
f[4733] = 583443000;
f[4734] = 585252864;
f[4735] = 585937500;
f[4736] = 587202560;
f[4737] = 587865600;
f[4738] = 588000000;
f[4739] = 588110544;
f[4740] = 588245000;
f[4741] = 589824000;
f[4742] = 590069760;
f[4743] = 590490000;
f[4744] = 590625000;
f[4745] = 592704000;
f[4746] = 592950960;
f[4747] = 594542592;
f[4748] = 595213920;
f[4749] = 595350000;
f[4750] = 597196800;
f[4751] = 597445632;
f[4752] = 597871125;
f[4753] = 600000000;
f[4754] = 600112800;
f[4755] = 600250000;
f[4756] = 600362847;
f[4757] = 602112000;
f[4758] = 602362880;
f[4759] = 602654094;
f[4760] = 602791875;
f[4761] = 603979776;
f[4762] = 604661760;
f[4763] = 604800000;
f[4764] = 605052000;
f[4765] = 605304105;
f[4766] = 606928896;
f[4767] = 607500000;
f[4768] = 607614210;
f[4769] = 607753125;
f[4770] = 609638400;
f[4771] = 609892416;
f[4772] = 612220032;
f[4773] = 612360000;
f[4774] = 612500000;
f[4775] = 612615150;
f[4776] = 614400000;
f[4777] = 614656000;
f[4778] = 615093750;
f[4779] = 615234375;
f[4780] = 616562688;
f[4781] = 617258880;
f[4782] = 617400000;
f[4783] = 617657250;
f[4784] = 619315200;
f[4785] = 619573248;
f[4786] = 620014500;
f[4787] = 620156250;
f[4788] = 622080000;
f[4789] = 622339200;
f[4790] = 622598508;
f[4791] = 624974616;
f[4792] = 625000000;
f[4793] = 625117500;
f[4794] = 627056640;
f[4795] = 627200000;
f[4796] = 629145600;
f[4797] = 629407744;
f[4798] = 629856000;
f[4799] = 630000000;
f[4800] = 630118440;
f[4801] = 630262500;
f[4802] = 632217600;
f[4803] = 632481024;
f[4804] = 632812500;
f[4805] = 634894848;
f[4806] = 635040000;
f[4807] = 635304600;
f[4808] = 637009920;
f[4809] = 637729200;
f[4810] = 637875000;
f[4811] = 640000000;
f[4812] = 640120320;
f[4813] = 642252800;
f[4814] = 642978000;
f[4815] = 643125000;
f[4816] = 644972544;
f[4817] = 645120000;
f[4818] = 645388800;
f[4819] = 645657712;
f[4820] = 645700815;
f[4821] = 648000000;
f[4822] = 648121824;
f[4823] = 648270000;
f[4824] = 650280960;
f[4825] = 651015225;
f[4826] = 653184000;
f[4827] = 653456160;
f[4828] = 655360000;
f[4829] = 656100000;
f[4830] = 656250000;
f[4831] = 656373375;
f[4832] = 658409472;
f[4833] = 658560000;
f[4834] = 658834400;
f[4835] = 660602880;
f[4836] = 661348800;
f[4837] = 661500000;
f[4838] = 661624362;
f[4839] = 661775625;
f[4840] = 663552000;
f[4841] = 663828480;
f[4842] = 664301250;
f[4843] = 664453125;
f[4844] = 666792000;
f[4845] = 667069830;
f[4846] = 668860416;
f[4847] = 669615660;
f[4848] = 669768750;
f[4849] = 669921875;
f[4850] = 671088640;
f[4851] = 671846400;
f[4852] = 672000000;
f[4853] = 672126336;
f[4854] = 672280000;
f[4855] = 674365440;
f[4856] = 675000000;
f[4857] = 675126900;
f[4858] = 675281250;
f[4859] = 677376000;
f[4860] = 677658240;
f[4861] = 679477248;
f[4862] = 680244480;
f[4863] = 680400000;
f[4864] = 680683500;
f[4865] = 682795008;
f[4866] = 683437500;
f[4867] = 683593750;
f[4868] = 685843200;
f[4869] = 686000000;
f[4870] = 686128968;
f[4871] = 688128000;
f[4872] = 688414720;
f[4873] = 688747536;
f[4874] = 688905000;
f[4875] = 689062500;
f[4876] = 691200000;
f[4877] = 691488000;
f[4878] = 691776120;
f[4879] = 693633024;
f[4880] = 694416240;
f[4881] = 694575000;
f[4882] = 696729600;
f[4883] = 697019904;
f[4884] = 699840000;
f[4885] = 700000000;
f[4886] = 700131600;
f[4887] = 702464000;
f[4888] = 703096443;
f[4889] = 703125000;
f[4890] = 704643072;
f[4891] = 705438720;
f[4892] = 705600000;
f[4893] = 705894000;
f[4894] = 707788800;
f[4895] = 708083712;
f[4896] = 708588000;
f[4897] = 708750000;
f[4898] = 708883245;
f[4899] = 711244800;
f[4900] = 711541152;
f[4901] = 714256704;
f[4902] = 714420000;
f[4903] = 714717675;
f[4904] = 716636160;
f[4905] = 716800000;
f[4906] = 717445350;
f[4907] = 717609375;
f[4908] = 719323136;
f[4909] = 720000000;
f[4910] = 720135360;
f[4911] = 720300000;
f[4912] = 720600125;
f[4913] = 722534400;
f[4914] = 722835456;
f[4915] = 723350250;
f[4916] = 723515625;
f[4917] = 725594112;
f[4918] = 725760000;
f[4919] = 726062400;
f[4920] = 726364926;
f[4921] = 729000000;
f[4922] = 729137052;
f[4923] = 729303750;
f[4924] = 731566080;
f[4925] = 732421875;
f[4926] = 734003200;
f[4927] = 734832000;
f[4928] = 735000000;
f[4929] = 735138180;
f[4930] = 735306250;
f[4931] = 737280000;
f[4932] = 737587200;
f[4933] = 737894528;
f[4934] = 738112500;
f[4935] = 738281250;
f[4936] = 740710656;
f[4937] = 740880000;
f[4938] = 741188700;
f[4939] = 743178240;
f[4940] = 744017400;
f[4941] = 744187500;
f[4942] = 746496000;
f[4943] = 746807040;
f[4944] = 750000000;
f[4945] = 750141000;
f[4946] = 750312500;
f[4947] = 752467968;
f[4948] = 752640000;
f[4949] = 752953600;
f[4950] = 754974720;
f[4951] = 755827200;
f[4952] = 756000000;
f[4953] = 756142128;
f[4954] = 756315000;
f[4955] = 758661120;
f[4956] = 759375000;
f[4957] = 762048000;
f[4958] = 762365520;
f[4959] = 764411904;
f[4960] = 765275040;
f[4961] = 765450000;
f[4962] = 765625000;
f[4963] = 768000000;
f[4964] = 768144384;
f[4965] = 768320000;
f[4966] = 770703360;
f[4967] = 771573600;
f[4968] = 771750000;
f[4969] = 771895089;
f[4970] = 774144000;
f[4971] = 774466560;
f[4972] = 774840978;
f[4973] = 775018125;
f[4974] = 777600000;
f[4975] = 777924000;
f[4976] = 778248135;
f[4977] = 780337152;
f[4978] = 781218270;
f[4979] = 781250000;
f[4980] = 781396875;
f[4981] = 783820800;
f[4982] = 784000000;
f[4983] = 784147392;
f[4984] = 786432000;
f[4985] = 786759680;
f[4986] = 787320000;
f[4987] = 787500000;
f[4988] = 787648050;
f[4989] = 787828125;
f[4990] = 790272000;
f[4991] = 790601280;
f[4992] = 791015625;
f[4993] = 792723456;
f[4994] = 793618560;
f[4995] = 793800000;
f[4996] = 794130750;
f[4997] = 796262400;
f[4998] = 796594176;
f[4999] = 797161500;
f[5000] = 797343750;
f[5001] = 800000000;
f[5002] = 800150400;
f[5003] = 800483796;
f[5004] = 802816000;
f[5005] = 803538792;
f[5006] = 803722500;
f[5007] = 803906250;
f[5008] = 805306368;
f[5009] = 806215680;
f[5010] = 806400000;
f[5011] = 806736000;
f[5012] = 807072140;
f[5013] = 809238528;
f[5014] = 810000000;
f[5015] = 810152280;
f[5016] = 810337500;
f[5017] = 812851200;
f[5018] = 813189888;
f[5019] = 816293376;
f[5020] = 816480000;
f[5021] = 816820200;
f[5022] = 819200000;
f[5023] = 820125000;
f[5024] = 820312500;
f[5025] = 822083584;
f[5026] = 823011840;
f[5027] = 823200000;
f[5028] = 823543000;
f[5029] = 825753600;
f[5030] = 826097664;
f[5031] = 826686000;
f[5032] = 826875000;
f[5033] = 829440000;
f[5034] = 829785600;
f[5035] = 830131344;
f[5036] = 833299488;
f[5037] = 833490000;
f[5038] = 836075520;
f[5039] = 837019575;
f[5040] = 838860800;
f[5041] = 839808000;
f[5042] = 840000000;
f[5043] = 840157920;
f[5044] = 840350000;
f[5045] = 842956800;
f[5046] = 843308032;
f[5047] = 843750000;
f[5048] = 843908625;
f[5049] = 846526464;
f[5050] = 846720000;
f[5051] = 847072800;
f[5052] = 847425747;
f[5053] = 849346560;
f[5054] = 850305600;
f[5055] = 850500000;
f[5056] = 850659894;
f[5057] = 850854375;
f[5058] = 853493760;
f[5059] = 854296875;
f[5060] = 857304000;
f[5061] = 857500000;
f[5062] = 857661210;
f[5063] = 859963392;
f[5064] = 860160000;
f[5065] = 860518400;
f[5066] = 860934420;
f[5067] = 861131250;
f[5068] = 861328125;
f[5069] = 864000000;
f[5070] = 864162432;
f[5071] = 864360000;
f[5072] = 864720150;
f[5073] = 867041280;
f[5074] = 868020300;
f[5075] = 868218750;
f[5076] = 870912000;
f[5077] = 871274880;
f[5078] = 874800000;
f[5079] = 875000000;
f[5080] = 875164500;
f[5081] = 877879296;
f[5082] = 878080000;
f[5083] = 878906250;
f[5084] = 880803840;
f[5085] = 881798400;
f[5086] = 882000000;
f[5087] = 882165816;
f[5088] = 882367500;
f[5089] = 884736000;
f[5090] = 885104640;
f[5091] = 885735000;
f[5092] = 885937500;
f[5093] = 889056000;
f[5094] = 889426440;
f[5095] = 891813888;
f[5096] = 892820880;
f[5097] = 893025000;
f[5098] = 895795200;
f[5099] = 896000000;
f[5100] = 896168448;
f[5101] = 899153920;
f[5102] = 900000000;
f[5103] = 900169200;
f[5104] = 900375000;
f[5105] = 903168000;
f[5106] = 903544320;
f[5107] = 903981141;
f[5108] = 905969664;
f[5109] = 906992640;
f[5110] = 907200000;
f[5111] = 907578000;
f[5112] = 910393344;
f[5113] = 911250000;
f[5114] = 911421315;
f[5115] = 914457600;
f[5116] = 914838624;
f[5117] = 917504000;
f[5118] = 918330048;
f[5119] = 918540000;
f[5120] = 918750000;
f[5121] = 918922725;
f[5122] = 921600000;
f[5123] = 921984000;
f[5124] = 922368160;
f[5125] = 922640625;
f[5126] = 924844032;
f[5127] = 925888320;
f[5128] = 926100000;
f[5129] = 926485875;
f[5130] = 928972800;
f[5131] = 929359872;
f[5132] = 930021750;
f[5133] = 930234375;
f[5134] = 933120000;
f[5135] = 933508800;
f[5136] = 933897762;
f[5137] = 937461924;
f[5138] = 937500000;
f[5139] = 937676250;
f[5140] = 937890625;
f[5141] = 939524096;
f[5142] = 940584960;
f[5143] = 940800000;
f[5144] = 941192000;
f[5145] = 943718400;
f[5146] = 944111616;
f[5147] = 944784000;
f[5148] = 945000000;
f[5149] = 945177660;
f[5150] = 945393750;
f[5151] = 948326400;
f[5152] = 948721536;
f[5153] = 949218750;
f[5154] = 952342272;
f[5155] = 952560000;
f[5156] = 952956900;
f[5157] = 955514880;
f[5158] = 956593800;
f[5159] = 956812500;
f[5160] = 957031250;
f[5161] = 960000000;
f[5162] = 960180480;
f[5163] = 960400000;
f[5164] = 963379200;
f[5165] = 963780608;
f[5166] = 964467000;
f[5167] = 964687500;
f[5168] = 967458816;
f[5169] = 967680000;
f[5170] = 968083200;
f[5171] = 968486568;
f[5172] = 972000000;
f[5173] = 972182736;
f[5174] = 972405000;
f[5175] = 975421440;
f[5176] = 976562500;
f[5177] = 979776000;
f[5178] = 980000000;
f[5179] = 980184240;
f[5180] = 983040000;
f[5181] = 983449600;
f[5182] = 984150000;
f[5183] = 984375000;
f[5184] = 987614208;
f[5185] = 987840000;
f[5186] = 988251600;
f[5187] = 990904320;
f[5188] = 992023200;
f[5189] = 992250000;
f[5190] = 992436543;
f[5191] = 995328000;
f[5192] = 995742720;
f[5193] = 996451875;
f[5194] = 1000000000;
f[5195] = 1000188000;
f[5196] = 1000604745;
f[5197] = 1003290624;
f[5198] = 1003520000;
f[5199] = 1004423490;
f[5200] = 1004653125;
f[5201] = 1006632960;
f[5202] = 1007769600;
f[5203] = 1008000000;
f[5204] = 1008189504;
f[5205] = 1008420000;
f[5206] = 1008840175;
f[5207] = 1011548160;
f[5208] = 1012500000;
f[5209] = 1012690350;
f[5210] = 1012921875;
f[5211] = 1016064000;
f[5212] = 1016487360;
f[5213] = 1019215872;
f[5214] = 1020366720;
f[5215] = 1020600000;
f[5216] = 1021025250;
f[5217] = 1024000000;
f[5218] = 1024192512;
f[5219] = 1025156250;
f[5220] = 1025390625;
f[5221] = 1027604480;
f[5222] = 1028764800;
f[5223] = 1029000000;
f[5224] = 1029193452;
f[5225] = 1029428750;
f[5226] = 1032192000;
f[5227] = 1032622080;
f[5228] = 1033121304;
f[5229] = 1033357500;
f[5230] = 1033593750;
f[5231] = 1036800000;
f[5232] = 1037232000;
f[5233] = 1037664180;
f[5234] = 1040449536;
f[5235] = 1041624360;
f[5236] = 1041862500;
f[5237] = 1045094400;
f[5238] = 1045529856;
f[5239] = 1048576000;
f[5240] = 1049760000;
f[5241] = 1050000000;
f[5242] = 1050197400;
f[5243] = 1050437500;
f[5244] = 1053696000;
f[5245] = 1054135040;
f[5246] = 1054687500;
f[5247] = 1056964608;
f[5248] = 1058158080;
f[5249] = 1058400000;
f[5250] = 1058841000;
f[5251] = 1061683200;
f[5252] = 1062125568;
f[5253] = 1062882000;
f[5254] = 1063125000;
f[5255] = 1066867200;
f[5256] = 1067311728;
f[5257] = 1071385056;
f[5258] = 1071630000;
f[5259] = 1071875000;
f[5260] = 1073741824;
f[5261] = 1074954240;
f[5262] = 1075200000;
f[5263] = 1075648000;
f[5264] = 1076168025;
f[5265] = 1078984704;
f[5266] = 1080000000;
f[5267] = 1080203040;
f[5268] = 1080450000;
f[5269] = 1083801600;
f[5270] = 1084253184;
f[5271] = 1085025375;
f[5272] = 1088391168;
f[5273] = 1088640000;
f[5274] = 1089093600;
f[5275] = 1089547389;
f[5276] = 1093500000;
f[5277] = 1093705578;
f[5278] = 1093750000;
f[5279] = 1093955625;
f[5280] = 1097349120;
f[5281] = 1097600000;
f[5282] = 1101004800;
f[5283] = 1101463552;
f[5284] = 1102248000;
f[5285] = 1102500000;
f[5286] = 1102707270;
f[5287] = 1102959375;
f[5288] = 1105920000;
f[5289] = 1106380800;
f[5290] = 1106841792;
f[5291] = 1107168750;
f[5292] = 1107421875;
f[5293] = 1111065984;
f[5294] = 1111320000;
f[5295] = 1111783050;
f[5296] = 1114767360;
f[5297] = 1116026100;
f[5298] = 1116281250;
f[5299] = 1119744000;
f[5300] = 1120000000;
f[5301] = 1120210560;
f[5302] = 1123942400;
f[5303] = 1125000000;
f[5304] = 1125211500;
f[5305] = 1125468750;
f[5306] = 1128701952;
f[5307] = 1128960000;
f[5308] = 1129430400;
f[5309] = 1129900996;
f[5310] = 1132462080;
f[5311] = 1133740800;
f[5312] = 1134000000;
f[5313] = 1134213192;
f[5314] = 1134472500;
f[5315] = 1137991680;
f[5316] = 1139062500;
f[5317] = 1143072000;
f[5318] = 1143548280;
f[5319] = 1146617856;
f[5320] = 1146880000;
f[5321] = 1147912560;
f[5322] = 1148175000;
f[5323] = 1148437500;
f[5324] = 1152000000;
f[5325] = 1152216576;
f[5326] = 1152480000;
f[5327] = 1152960200;
f[5328] = 1156055040;
f[5329] = 1157360400;
f[5330] = 1157625000;
f[5331] = 1161216000;
f[5332] = 1161699840;
f[5333] = 1162261467;
f[5334] = 1166400000;
f[5335] = 1166886000;
f[5336] = 1170505728;
f[5337] = 1171827405;
f[5338] = 1171875000;
f[5339] = 1174405120;
f[5340] = 1175731200;
f[5341] = 1176000000;
f[5342] = 1176221088;
f[5343] = 1176490000;
f[5344] = 1179648000;
f[5345] = 1180139520;
f[5346] = 1180980000;
f[5347] = 1181250000;
f[5348] = 1181472075;
f[5349] = 1185408000;
f[5350] = 1185901920;
f[5351] = 1189085184;
f[5352] = 1190427840;
f[5353] = 1190700000;
f[5354] = 1191196125;
f[5355] = 1194393600;
f[5356] = 1194891264;
f[5357] = 1195742250;
f[5358] = 1196015625;
f[5359] = 1200000000;
f[5360] = 1200225600;
f[5361] = 1200500000;
f[5362] = 1200725694;
f[5363] = 1204224000;
f[5364] = 1204725760;
f[5365] = 1205308188;
f[5366] = 1205583750;
f[5367] = 1205859375;
f[5368] = 1207959552;
f[5369] = 1209323520;
f[5370] = 1209600000;
f[5371] = 1210104000;
f[5372] = 1210608210;
f[5373] = 1213857792;
f[5374] = 1215000000;
f[5375] = 1215228420;
f[5376] = 1215506250;
f[5377] = 1219276800;
f[5378] = 1219784832;
f[5379] = 1220703125;
f[5380] = 1224440064;
f[5381] = 1224720000;
f[5382] = 1225000000;
f[5383] = 1225230300;
f[5384] = 1228800000;
f[5385] = 1229312000;
f[5386] = 1230187500;
f[5387] = 1230468750;
f[5388] = 1233125376;
f[5389] = 1234517760;
f[5390] = 1234800000;
f[5391] = 1235314500;
f[5392] = 1238630400;
f[5393] = 1239146496;
f[5394] = 1240029000;
f[5395] = 1240312500;
f[5396] = 1244160000;
f[5397] = 1244678400;
f[5398] = 1245197016;
f[5399] = 1249949232;
f[5400] = 1250000000;
f[5401] = 1250235000;
f[5402] = 1254113280;
f[5403] = 1254400000;
f[5404] = 1258291200;
f[5405] = 1258815488;
f[5406] = 1259712000;
f[5407] = 1260000000;
f[5408] = 1260236880;
f[5409] = 1260525000;
f[5410] = 1264435200;
f[5411] = 1264962048;
f[5412] = 1265625000;
f[5413] = 1269789696;
f[5414] = 1270080000;
f[5415] = 1270609200;
f[5416] = 1274019840;
f[5417] = 1275458400;
f[5418] = 1275750000;
f[5419] = 1275989841;
f[5420] = 1280000000;
f[5421] = 1280240640;
f[5422] = 1284505600;
f[5423] = 1285956000;
f[5424] = 1286250000;
f[5425] = 1286491815;
f[5426] = 1289945088;
f[5427] = 1290240000;
f[5428] = 1290777600;
f[5429] = 1291315424;
f[5430] = 1291401630;
f[5431] = 1291696875;
f[5432] = 1296000000;
f[5433] = 1296243648;
f[5434] = 1296540000;
f[5435] = 1297080225;
f[5436] = 1300561920;
f[5437] = 1302030450;
f[5438] = 1302328125;
f[5439] = 1306368000;
f[5440] = 1306912320;
f[5441] = 1310720000;
f[5442] = 1312200000;
f[5443] = 1312500000;
f[5444] = 1312746750;
f[5445] = 1313046875;
f[5446] = 1316818944;
f[5447] = 1317120000;
f[5448] = 1317668800;
f[5449] = 1318359375;
f[5450] = 1321205760;
f[5451] = 1322697600;
f[5452] = 1323000000;
f[5453] = 1323248724;
f[5454] = 1323551250;
f[5455] = 1327104000;
f[5456] = 1327656960;
f[5457] = 1328602500;
f[5458] = 1328906250;
f[5459] = 1333584000;
f[5460] = 1334139660;
f[5461] = 1337720832;
f[5462] = 1339231320;
f[5463] = 1339537500;
f[5464] = 1339843750;
f[5465] = 1342177280;
f[5466] = 1343692800;
f[5467] = 1344000000;
f[5468] = 1344252672;
f[5469] = 1344560000;
f[5470] = 1348730880;
f[5471] = 1350000000;
f[5472] = 1350253800;
f[5473] = 1350562500;
f[5474] = 1354752000;
f[5475] = 1355316480;
f[5476] = 1358954496;
f[5477] = 1360488960;
f[5478] = 1360800000;
f[5479] = 1361367000;
f[5480] = 1365590016;
f[5481] = 1366875000;
f[5482] = 1367187500;
f[5483] = 1371686400;
f[5484] = 1372000000;
f[5485] = 1372257936;
f[5486] = 1376256000;
f[5487] = 1376829440;
f[5488] = 1377495072;
f[5489] = 1377810000;
f[5490] = 1378125000;
f[5491] = 1382400000;
f[5492] = 1382976000;
f[5493] = 1383552240;
f[5494] = 1387266048;
f[5495] = 1388832480;
f[5496] = 1389150000;
f[5497] = 1393459200;
f[5498] = 1394039808;
f[5499] = 1395032625;
f[5500] = 1399680000;
f[5501] = 1400000000;
f[5502] = 1400263200;
f[5503] = 1400846643;
f[5504] = 1404928000;
f[5505] = 1406192886;
f[5506] = 1406250000;
f[5507] = 1406514375;
f[5508] = 1409286144;
f[5509] = 1410877440;
f[5510] = 1411200000;
f[5511] = 1411788000;
f[5512] = 1412376245;
f[5513] = 1415577600;
f[5514] = 1416167424;
f[5515] = 1417176000;
f[5516] = 1417500000;
f[5517] = 1417766490;
f[5518] = 1418090625;
f[5519] = 1422489600;
f[5520] = 1423082304;
f[5521] = 1423828125;
f[5522] = 1428513408;
f[5523] = 1428840000;
f[5524] = 1429435350;
f[5525] = 1433272320;
f[5526] = 1433600000;
f[5527] = 1434890700;
f[5528] = 1435218750;
f[5529] = 1435546875;
f[5530] = 1438646272;
f[5531] = 1440000000;
f[5532] = 1440270720;
f[5533] = 1440600000;
f[5534] = 1441200250;
f[5535] = 1445068800;
f[5536] = 1445670912;
f[5537] = 1446700500;
f[5538] = 1447031250;
f[5539] = 1451188224;
f[5540] = 1451520000;
f[5541] = 1452124800;
f[5542] = 1452729852;
f[5543] = 1458000000;
f[5544] = 1458274104;
f[5545] = 1458607500;
f[5546] = 1463132160;
f[5547] = 1464843750;
f[5548] = 1468006400;
f[5549] = 1469664000;
f[5550] = 1470000000;
f[5551] = 1470276360;
f[5552] = 1470612500;
f[5553] = 1474560000;
f[5554] = 1475174400;
f[5555] = 1475789056;
f[5556] = 1476225000;
f[5557] = 1476562500;
f[5558] = 1481421312;
f[5559] = 1481760000;
f[5560] = 1482377400;
f[5561] = 1486356480;
f[5562] = 1488034800;
f[5563] = 1488375000;
f[5564] = 1492992000;
f[5565] = 1493614080;
f[5566] = 1500000000;
f[5567] = 1500282000;
f[5568] = 1500625000;
f[5569] = 1504935936;
f[5570] = 1505280000;
f[5571] = 1505907200;
f[5572] = 1506635235;
f[5573] = 1509949440;
f[5574] = 1511654400;
f[5575] = 1512000000;
f[5576] = 1512284256;
f[5577] = 1512630000;
f[5578] = 1517322240;
f[5579] = 1518750000;
f[5580] = 1519035525;
f[5581] = 1524096000;
f[5582] = 1524731040;
f[5583] = 1528823808;
f[5584] = 1530550080;
f[5585] = 1530900000;
f[5586] = 1531250000;
f[5587] = 1531537875;
f[5588] = 1536000000;
f[5589] = 1536288768;
f[5590] = 1536640000;
f[5591] = 1537734375;
f[5592] = 1541406720;
f[5593] = 1543147200;
f[5594] = 1543500000;
f[5595] = 1543790178;
f[5596] = 1544143125;
f[5597] = 1548288000;
f[5598] = 1548933120;
f[5599] = 1549681956;
f[5600] = 1550036250;
f[5601] = 1550390625;
f[5602] = 1555200000;
f[5603] = 1555848000;
f[5604] = 1556496270;
f[5605] = 1560674304;
f[5606] = 1562436540;
f[5607] = 1562500000;
f[5608] = 1562793750;
f[5609] = 1567641600;
f[5610] = 1568000000;
f[5611] = 1568294784;
f[5612] = 1572864000;
f[5613] = 1573519360;
f[5614] = 1574640000;
f[5615] = 1575000000;
f[5616] = 1575296100;
f[5617] = 1575656250;
f[5618] = 1580544000;
f[5619] = 1581202560;
f[5620] = 1582031250;
f[5621] = 1585446912;
f[5622] = 1587237120;
f[5623] = 1587600000;
f[5624] = 1588261500;
f[5625] = 1592524800;
f[5626] = 1593188352;
f[5627] = 1594323000;
f[5628] = 1594687500;
f[5629] = 1600000000;
f[5630] = 1600300800;
f[5631] = 1600967592;
f[5632] = 1605632000;
f[5633] = 1607077584;
f[5634] = 1607445000;
f[5635] = 1607812500;
f[5636] = 1610612736;
f[5637] = 1612431360;
f[5638] = 1612800000;
f[5639] = 1613472000;
f[5640] = 1614144280;
f[5641] = 1618477056;
f[5642] = 1620000000;
f[5643] = 1620304560;
f[5644] = 1620675000;
f[5645] = 1625702400;
f[5646] = 1626379776;
f[5647] = 1632586752;
f[5648] = 1632960000;
f[5649] = 1633640400;
f[5650] = 1638400000;
f[5651] = 1640250000;
f[5652] = 1640558367;
f[5653] = 1640625000;
f[5654] = 1644167168;
f[5655] = 1646023680;
f[5656] = 1646400000;
f[5657] = 1647086000;
f[5658] = 1651507200;
f[5659] = 1652195328;
f[5660] = 1653372000;
f[5661] = 1653750000;
f[5662] = 1654060905;
f[5663] = 1658880000;
f[5664] = 1659571200;
f[5665] = 1660262688;
f[5666] = 1660753125;
f[5667] = 1666598976;
f[5668] = 1666980000;
f[5669] = 1667674575;
f[5670] = 1672151040;
f[5671] = 1674039150;
f[5672] = 1674421875;
f[5673] = 1677721600;
f[5674] = 1679616000;
f[5675] = 1680000000;
f[5676] = 1680315840;
f[5677] = 1680700000;
f[5678] = 1685913600;
f[5679] = 1686616064;
f[5680] = 1687500000;
f[5681] = 1687817250;
f[5682] = 1688203125;
f[5683] = 1693052928;
f[5684] = 1693440000;
f[5685] = 1694145600;
f[5686] = 1694851494;
f[5687] = 1698693120;
f[5688] = 1700611200;
f[5689] = 1701000000;
f[5690] = 1701319788;
f[5691] = 1701708750;
f[5692] = 1706987520;
f[5693] = 1708593750;
f[5694] = 1708984375;
f[5695] = 1714608000;
f[5696] = 1715000000;
f[5697] = 1715322420;
f[5698] = 1719926784;
f[5699] = 1720320000;
f[5700] = 1721036800;
f[5701] = 1721868840;
f[5702] = 1722262500;
f[5703] = 1722656250;
f[5704] = 1728000000;
f[5705] = 1728324864;
f[5706] = 1728720000;
f[5707] = 1729440300;
f[5708] = 1734082560;
f[5709] = 1736040600;
f[5710] = 1736437500;
f[5711] = 1741824000;
f[5712] = 1742549760;
f[5713] = 1749600000;
f[5714] = 1750000000;
f[5715] = 1750329000;
f[5716] = 1755758592;
f[5717] = 1756160000;
f[5718] = 1757812500;
f[5719] = 1761607680;
f[5720] = 1763596800;
f[5721] = 1764000000;
f[5722] = 1764331632;
f[5723] = 1764735000;
f[5724] = 1769472000;
f[5725] = 1770209280;
f[5726] = 1771470000;
f[5727] = 1771875000;
f[5728] = 1778112000;
f[5729] = 1778852880;
f[5730] = 1783627776;
f[5731] = 1785641760;
f[5732] = 1786050000;
f[5733] = 1791590400;
f[5734] = 1792000000;
f[5735] = 1792336896;
f[5736] = 1793613375;
f[5737] = 1798307840;
f[5738] = 1800000000;
f[5739] = 1800338400;
f[5740] = 1800750000;
f[5741] = 1801088541;
f[5742] = 1806336000;
f[5743] = 1807088640;
f[5744] = 1807962282;
f[5745] = 1808375625;
f[5746] = 1811939328;
f[5747] = 1813985280;
f[5748] = 1814400000;
f[5749] = 1815156000;
f[5750] = 1815912315;
f[5751] = 1820786688;
f[5752] = 1822500000;
f[5753] = 1822842630;
f[5754] = 1823259375;
f[5755] = 1828915200;
f[5756] = 1829677248;
f[5757] = 1835008000;
f[5758] = 1836660096;
f[5759] = 1837080000;
f[5760] = 1837500000;
f[5761] = 1837845450;
f[5762] = 1838265625;
f[5763] = 1843200000;
f[5764] = 1843968000;
f[5765] = 1844736320;
f[5766] = 1845281250;
f[5767] = 1845703125;
f[5768] = 1849688064;
f[5769] = 1851776640;
f[5770] = 1852200000;
f[5771] = 1852971750;
f[5772] = 1857945600;
f[5773] = 1858719744;
f[5774] = 1860043500;
f[5775] = 1860468750;
f[5776] = 1866240000;
f[5777] = 1867017600;
f[5778] = 1867795524;
f[5779] = 1874923848;
f[5780] = 1875000000;
f[5781] = 1875352500;
f[5782] = 1875781250;
f[5783] = 1879048192;
f[5784] = 1881169920;
f[5785] = 1881600000;
f[5786] = 1882384000;
f[5787] = 1887436800;
f[5788] = 1888223232;
f[5789] = 1889568000;
f[5790] = 1890000000;
f[5791] = 1890355320;
f[5792] = 1890787500;
f[5793] = 1896652800;
f[5794] = 1897443072;
f[5795] = 1898437500;
f[5796] = 1904684544;
f[5797] = 1905120000;
f[5798] = 1905913800;
f[5799] = 1911029760;
f[5800] = 1913187600;
f[5801] = 1913625000;
f[5802] = 1914062500;
f[5803] = 1920000000;
f[5804] = 1920360960;
f[5805] = 1920800000;
f[5806] = 1926758400;
f[5807] = 1927561216;
f[5808] = 1928934000;
f[5809] = 1929375000;
f[5810] = 1934917632;
f[5811] = 1935360000;
f[5812] = 1936166400;
f[5813] = 1936973136;
f[5814] = 1937102445;
f[5815] = 1944000000;
f[5816] = 1944365472;
f[5817] = 1944810000;
f[5818] = 1950842880;
f[5819] = 1953045675;
f[5820] = 1953125000;
f[5821] = 1959552000;
f[5822] = 1960000000;
f[5823] = 1960368480;
f[5824] = 1966080000;
f[5825] = 1966899200;
f[5826] = 1968300000;
f[5827] = 1968750000;
f[5828] = 1969120125;
f[5829] = 1975228416;
f[5830] = 1975680000;
f[5831] = 1976503200;
f[5832] = 1977326743;
f[5833] = 1981808640;
f[5834] = 1984046400;
f[5835] = 1984500000;
f[5836] = 1984873086;
f[5837] = 1985326875;
f[5838] = 1990656000;
f[5839] = 1991485440;
f[5840] = 1992903750;
f[5841] = 1993359375;
f[5842] = 2000000000;
/*
freopen("result.out", "w", stdout);
choufilter();
for (int i = 1; num[i]; i++)
{
printf("f[%d]=", i);
cout << num[i] << ";" << endl;
}
fclose(stdout);
*/
int n;
while (cin >> n,n!=0)
{
cout << f[n] << endl;
}
return 0;
}
Accepted Code
#include <bits/stdc++.h>
using namespace std;
#define min4(a,b,c,d) min(min(a,b),min(c,d))
int num[6000];
int p2=1,p3=1,p5=1,p7=1; //p2 p3 p5 p7用以指示上一个数是以2 3 5 7其一所生成
int main()
{
num[1]=1;
num[2]=2;
num[3]=3;
num[4]=5;
num[5]=7;
for (int i = 2; i < 6000; i++)
{
int tmp;
tmp=min4(num[p2]*2,num[p3]*3,num[p5]*5,num[p7]*7);
if(tmp%2==0)
{
p2++;
}
if(tmp%3==0)
{
p3++;
}
if(tmp%5==0)
{
p5++;
}
if(tmp%7==0)
{
p7++;
}
num[i]=tmp;
}
int n;
while(cin>>n,n!=0)
{
cout<<num[n]<<endl;
}
return 0;
}
解后反思
要大胆地尝试打表计算，关于丑数本身的运算也就是一个状态转移的过程（待更新）
大佬顶