int lis[10005]=
{
0
,1000,1001,1008,1421,1909,1089,1085,1035,1980,1014,1307,1046,1047,2141,5015,1055,1308,2010,1012,1028,1036,1464,1192,1025,1003,1067,1328,1563,1042,1179,2615,1177,1059,1068,1051,1309,1908
,1378,1219,1019,5194,1162,1032,1126,1443,3956,1024,2678,1314,1316,1083,1902,1226,1010,1257,3612,1996,1160,1449,1739,1981,1175,1540,1087,1030,1305,1229,1090,1208,1094,1080,1199,2672,1216
,1020,1091,1005,1095,1541,1868,1048,1049,1060,5020,1064,2946,1855,1156,1601,2142,1303,1480,3146,2466,4302,1880,1063,1352,2014,1040,1122,1514,1535,1434,3953,1120,1312,1074,3383,4718,1865
,1029,2152,1072,2158,2568,2398,4549,2613,1082,3951,1516,1414,2197,1288,1290,1247,2252,3374,3368,1908,1966,1972,3586,4054,4113,3372,3373,1502,2471,1382,1471,4198,3722,2824,4097,4513,1111
,3958,2024,1197,1196,1955,1525,3378,1168,2827,2085,2661,2921,3371,4779,1144,5001,1462,1522,1266,2195,3629,1099,3379,3938,4281,3366,1546,2330,1991,1967,1113,1983,1038,3275,2294,4926,3387
,3388,2863,2746,2341,2515,3870,1972,1494,3396,1903,1975,3710,4074,4168,4119,4117,3806,2634,2664,4292,4149,3241,2468,3302,3168,4559,4618,2633,3293,3369,3391,3285,3850,4008,2042,1110,3644
,3765,1486,3224,3960,3384,3313,2590,2486,2146,3613,3178,3258,4069,4211,3380,1975,3332,4278,1903,3759,3242,3248,3690,3203,1501,4338,4312,2387,3348,3703,4172,4219,3810,1393,2617,3332,4169
,3835,3919,5055,3834,3402,2704,1879,1896,2051,2150,2157,2167,4925,3648,4363,5005,2396,1081,1613,5024,4719,4751,3572,3522,4544,2305,2900,3195,3628,4027,4767,2602,3281,2518,2657,3286,2606
,5056,2289,2337,1850,2081,3600,3830,4564,2473,2221,3317,3343,4284,5104,5249,3390,1939,1962,1349,4000,4783,4035,4111,4208,4387,4457,3812,3857,4151,4301,3292,3807,2822,1655,3197,2290,4931
,3214,3978,1919,3803,4238,4239,4245,4717,4721,4091,4461,3338,3723,3768,3172,3455,3327,4619,3370,5270,3375,4391,3435,2375,3426,3193,3435,3805,4555,1659,2292,2922,3065,3294,3783,3879,4551
,4407,4683,3808,3796,3121,2414,3966,2444,3311,4052,3809,1117,2178,2463,4051,2336,2852,3804,4770,3649,3975,4248,3067,4799,5195,1379,2324,3386,2756,1559,2055,2825,3033,3731,3376,1345,2774
,2763,2472,2065,2765,2764,2766,2805,3749,5039,3381,2153,2053,3159,4016,4249,4452,2604,2050,3980,4782,3825,2495,3233,1337,2503,3878,4360,3199,3288,3705,4322,4377,1335,1737,3614,3640,3782
,3836,4920
};