NEFU-574 丑数

NEFU-574 丑数

/ 1评 / 947次 / 0

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;
}

解后反思

要大胆地尝试打表计算,关于丑数本身的运算也就是一个状态转移的过程(待更新)

《“NEFU-574 丑数”》 有 1 条评论

发表回复

您的电子邮箱地址不会被公开。

你好 No.59613