这题很简单，暴力打表即可

#include <bits/stdc++.h>

using namespace std;

int n;

int main ()
{
	cin >> n;
	if (n == 1) cout << 1;
	else if (n == 2) cout << 1;
	else if (n == 3) cout << 1;
	else if (n == 4) cout << 2;
	else if (n == 5) cout << 2;
	else if (n == 6) cout << 2;
	else if (n == 7) cout << 2;
	else if (n == 8) cout << 3;
	else if (n == 9) cout << 4;
	else if (n == 10) cout << 4;
	else if (n == 11) cout << 4;
	else if (n == 12) cout << 5;
	else if (n == 13) cout << 6;
	else if (n == 14) cout << 6;
	else if (n == 15) cout << 6;
	else if (n == 16) cout << 8;
	else if (n == 17) cout << 9;
	else if (n == 18) cout << 10;
	else if (n == 19) cout << 10;
	else if (n == 20) cout << 12;
	else if (n == 21) cout << 13;
	else if (n == 22) cout << 14;
	else if (n == 23) cout << 14;
	else if (n == 24) cout << 16;
	else if (n == 25) cout << 19;
	else if (n == 26) cout << 20;
	else if (n == 27) cout << 21;
	else if (n == 28) cout << 23;
	else if (n == 29) cout << 26;
	else if (n == 30) cout << 27;
	else if (n == 31) cout << 28;
	else if (n == 32) cout << 31;
	else if (n == 33) cout << 34;
	else if (n == 34) cout << 37;
	else if (n == 35) cout << 38;
	else if (n == 36) cout << 43;
	else if (n == 37) cout << 46;
	else if (n == 38) cout << 49;
	else if (n == 39) cout << 50;
	else if (n == 40) cout << 55;
	else if (n == 41) cout << 60;
	else if (n == 42) cout << 63;
	else if (n == 43) cout << 66;
	else if (n == 44) cout << 71;
	else if (n == 45) cout << 78;
	else if (n == 46) cout << 81;
	else if (n == 47) cout << 84;
	else if (n == 48) cout << 90;
	else if (n == 49) cout << 98;
	else if (n == 50) cout << 104;
	else if (n == 51) cout << 107;
	else if (n == 52) cout << 116;
	else if (n == 53) cout << 124;
	else if (n == 54) cout << 132;
	else if (n == 55) cout << 135;
	else if (n == 56) cout << 144;
	else if (n == 57) cout << 154;
	else if (n == 58) cout << 163;
	else if (n == 59) cout << 169;
	else if (n == 60) cout << 178;
	else if (n == 61) cout << 192;
	else if (n == 62) cout << 201;
	else if (n == 63) cout << 209;
	else if (n == 64) cout << 220;
	else if (n == 65) cout << 235;
	else if (n == 66) cout << 247;
	else if (n == 67) cout << 256;
	else if (n == 68) cout << 271;
	else if (n == 69) cout << 286;
	else if (n == 70) cout << 302;
	else if (n == 71) cout << 311;
	else if (n == 72) cout << 329;
	else if (n == 73) cout << 347;
	else if (n == 74) cout << 365;
	else if (n == 75) cout << 378;
	else if (n == 76) cout << 397;
	else if (n == 77) cout << 420;
	else if (n == 78) cout << 438;
	else if (n == 79) cout << 455;
	else if (n == 80) cout << 476;
	else if (n == 81) cout << 504;
	else if (n == 82) cout << 526;
	else if (n == 83) cout << 545;
	else if (n == 84) cout << 571;
	else if (n == 85) cout << 601;
	else if (n == 86) cout << 629;
	else if (n == 87) cout << 648;
	else if (n == 88) cout << 679;
	else if (n == 89) cout << 713;
	else if (n == 90) cout << 747;
	else if (n == 91) cout << 771;
	else if (n == 92) cout << 804;
	else if (n == 93) cout << 844;
	else if (n == 94) cout << 880;
	else if (n == 95) cout << 910;
	else if (n == 96) cout << 945;
	else if (n == 97) cout << 993;
	else if (n == 98) cout << 1035;
	else if (n == 99) cout << 1072;
	else if (n == 100) cout << 1116;
	else if (n == 101) cout << 1167;
	else if (n == 102) cout << 1216;
	else if (n == 103) cout << 1255;
	else if (n == 104) cout << 1306;
	else if (n == 105) cout << 1361;
	else if (n == 106) cout << 1420;
	else if (n == 107) cout << 1466;
	else if (n == 108) cout << 1525;
	else if (n == 109) cout << 1590;
	else if (n == 110) cout << 1653;
	else if (n == 111) cout << 1707;
	else if (n == 112) cout << 1770;
	else if (n == 113) cout << 1846;
	else if (n == 114) cout << 1916;
	else if (n == 115) cout << 1981;
	else if (n == 116) cout << 2055;
	else if (n == 117) cout << 2141;
	else if (n == 118) cout << 2222;
	else if (n == 119) cout << 2291;
	else if (n == 120) cout << 2374;
	else if (n == 121) cout << 2468;
	else if (n == 122) cout << 2563;
	else if (n == 123) cout << 2641;
	else if (n == 124) cout << 2737;
	else if (n == 125) cout << 2846;
	else if (n == 126) cout << 2952;
	else if (n == 127) cout << 3042;
	else if (n == 128) cout << 3145;
	else if (n == 129) cout << 3267;
	else if (n == 130) cout << 3385;
	else if (n == 131) cout << 3491;
	else if (n == 132) cout << 3607;
	else if (n == 133) cout << 3745;
	else if (n == 134) cout << 3880;
	else if (n == 135) cout << 3998;
	else if (n == 136) cout << 4130;
	else if (n == 137) cout << 4279;
	else if (n == 138) cout << 4431;
	else if (n == 139) cout << 4564;
	else if (n == 140) cout << 4714;
	else if (n == 141) cout << 4880;
	else if (n == 142) cout << 5050;
	else if (n == 143) cout << 5201;
	else if (n == 144) cout << 5368;
	else if (n == 145) cout << 5555;
	else if (n == 146) cout << 5742;
	else if (n == 147) cout << 5914;
	else if (n == 148) cout << 6101;
	else if (n == 149) cout << 6312;
	else if (n == 150) cout << 6521;
	else if (n == 151) cout << 6712;
	else if (n == 152) cout << 6921;
	else if (n == 153) cout << 7155;
	else if (n == 154) cout << 7389;
	else if (n == 155) cout << 7601;
	else if (n == 156) cout << 7834;
	else if (n == 157) cout << 8094;
	else if (n == 158) cout << 8355;
	else if (n == 159) cout << 8591;
	else if (n == 160) cout << 8849;
	else if (n == 161) cout << 9139;
	else if (n == 162) cout << 9431;
	else if (n == 163) cout << 9697;
	else if (n == 164) cout << 9984;
	else if (n == 165) cout << 10304;
	else if (n == 166) cout << 10628;
	else if (n == 167) cout << 10923;
	else if (n == 168) cout << 11238;
	else if (n == 169) cout << 11592;
	else if (n == 170) cout << 11953;
	else if (n == 171) cout << 12285;
	else if (n == 172) cout << 12637;
	else if (n == 173) cout << 13027;
	else if (n == 174) cout << 13424;
	else if (n == 175) cout << 13793;
	else if (n == 176) cout << 14180;
	else if (n == 177) cout << 14607;
	else if (n == 178) cout << 15048;
	else if (n == 179) cout << 15460;
	else if (n == 180) cout << 15895;
	else if (n == 181) cout << 16368;
	else if (n == 182) cout << 16853;
	else if (n == 183) cout << 17305;
	else if (n == 184) cout << 17782;
	else if (n == 185) cout << 18303;
	else if (n == 186) cout << 18835;
	else if (n == 187) cout << 19339;
	else if (n == 188) cout << 19867;
	else if (n == 189) cout << 20447;
	else if (n == 190) cout << 21031;
	else if (n == 191) cout << 21585;
	else if (n == 192) cout << 22161;
	else if (n == 193) cout << 22795;
	else if (n == 194) cout << 23441;
	else if (n == 195) cout << 24051;
	else if (n == 196) cout << 24694;
	else if (n == 197) cout << 25392;
	else if (n == 198) cout << 26109;
	else if (n == 199) cout << 26778;
	else if (n == 200) cout << 27482;
	else if (n == 201) cout << 28241;
	else if (n == 202) cout << 29025;
	else if (n == 203) cout << 29766;
	else if (n == 204) cout << 30535;
	else if (n == 205) cout << 31376;
	else if (n == 206) cout << 32235;
	else if (n == 207) cout << 33055;
	else if (n == 208) cout << 33896;
	else if (n == 209) cout << 34812;
	else if (n == 210) cout << 35750;
	else if (n == 211) cout << 36651;
	else if (n == 212) cout << 37581;
	else if (n == 213) cout << 38578;
	else if (n == 214) cout << 39614;
	else if (n == 215) cout << 40598;
	else if (n == 216) cout << 41621;
	else if (n == 217) cout << 42707;
	else if (n == 218) cout << 43835;
	else if (n == 219) cout << 44914;
	else if (n == 220) cout << 46030;
	else if (n == 221) cout << 47228;
	else if (n == 222) cout << 48452;
	else if (n == 223) cout << 49641;
	else if (n == 224) cout << 50856;
	else if (n == 225) cout << 52170;
	else if (n == 226) cout << 53503;
	else if (n == 227) cout << 54801;
	else if (n == 228) cout << 56133;
	else if (n == 229) cout << 57560;
	else if (n == 230) cout << 59027;
	else if (n == 231) cout << 60434;
	else if (n == 232) cout << 61894;
	else if (n == 233) cout << 63443;
	else if (n == 234) cout << 65049;
	else if (n == 235) cout << 66585;
	else if (n == 236) cout << 68174;
	else if (n == 237) cout << 69865;
	else if (n == 238) cout << 71604;
	else if (n == 239) cout << 73290;
	else if (n == 240) cout << 75005;
	else if (n == 241) cout << 76852;
	else if (n == 242) cout << 78741;
	else if (n == 243) cout << 80589;
	else if (n == 244) cout << 82465;
	else if (n == 245) cout << 84468;
	else if (n == 246) cout << 86529;
	else if (n == 247) cout << 88530;
	else if (n == 248) cout << 90578;
	else if (n == 249) cout << 92737;
	else if (n == 250) cout << 94987;
	else if (n == 251) cout << 97162;
	else if (n == 252) cout << 99397;
	else if (n == 253) cout << 101749;
	else if (n == 254) cout << 104180;
	else if (n == 255) cout << 106551;
	else if (n == 256) cout << 108963;
	else if (n == 257) cout << 111524;
	else if (n == 258) cout << 114146;
	else if (n == 259) cout << 116735;
	else if (n == 260) cout << 119360;
	else if (n == 261) cout << 122146;
	else if (n == 262) cout << 124997;
	else if (n == 263) cout << 127792;
	else if (n == 264) cout << 130643;
	else if (n == 265) cout << 133641;
	else if (n == 266) cout << 136742;
	else if (n == 267) cout << 139761;
	else if (n == 268) cout << 142864;
	else if (n == 269) cout << 146119;
	else if (n == 270) cout << 149482;
	else if (n == 271) cout << 152762;
	else if (n == 272) cout << 156106;
	else if (n == 273) cout << 159629;
	else if (n == 274) cout << 163250;
	else if (n == 275) cout << 166821;
	else if (n == 276) cout << 170432;
	else if (n == 277) cout << 174255;
	else if (n == 278) cout << 178180;
	else if (n == 279) cout << 182046;
	else if (n == 280) cout << 185960;
	else if (n == 281) cout << 190071;
	else if (n == 282) cout << 194315;
	else if (n == 283) cout << 198484;
	else if (n == 284) cout << 202729;
	else if (n == 285) cout << 207163;
	else if (n == 286) cout << 211756;
	else if (n == 287) cout << 216269;
	else if (n == 288) cout << 220852;
	else if (n == 289) cout << 225644;
	else if (n == 290) cout << 230580;
	else if (n == 291) cout << 235465;
	else if (n == 292) cout << 240408;
	else if (n == 293) cout << 245594;
	else if (n == 294) cout << 250916;
	else if (n == 295) cout << 256195;
	else if (n == 296) cout << 261537;
	else if (n == 297) cout << 267123;
	else if (n == 298) cout << 272865;
	else if (n == 299) cout << 278544;
	else if (n == 300) cout << 284316;
	else if (n == 301) cout << 290326;
	else if (n == 302) cout << 296525;
	else if (n == 303) cout << 302642;
	else if (n == 304) cout << 308862;
	else if (n == 305) cout << 315342;
	else if (n == 306) cout << 322017;
	else if (n == 307) cout << 328619;
	else if (n == 308) cout << 335313;
	else if (n == 309) cout << 342297;
	else if (n == 310) cout << 349475;
	else if (n == 311) cout << 356595;
	else if (n == 312) cout << 363790;
	else if (n == 313) cout << 371300;
	else if (n == 314) cout << 379029;
	else if (n == 315) cout << 386695;
	else if (n == 316) cout << 394450;
	else if (n == 317) cout << 402519;
	else if (n == 318) cout << 410832;
	else if (n == 319) cout << 419075;
	else if (n == 320) cout << 427416;
	else if (n == 321) cout << 436077;
	else if (n == 322) cout << 445009;
	else if (n == 323) cout << 453884;
	else if (n == 324) cout << 462865;
	else if (n == 325) cout << 472185;
	else if (n == 326) cout << 481771;
	else if (n == 327) cout << 491309;
	else if (n == 328) cout << 500949;
	else if (n == 329) cout << 510951;
	else if (n == 330) cout << 521232;
	else if (n == 331) cout << 531482;
	else if (n == 332) cout << 541848;
	else if (n == 333) cout << 552597;
	else if (n == 334) cout << 563635;
	else if (n == 335) cout << 574630;
	else if (n == 336) cout << 585750;
	else if (n == 337) cout << 597264;
	else if (n == 338) cout << 609101;
	else if (n == 339) cout << 620895;
	else if (n == 340) cout << 632840;
	else if (n == 341) cout << 645204;
	else if (n == 342) cout << 657915;
	else if (n == 343) cout << 670568;
	else if (n == 344) cout << 683368;
	else if (n == 345) cout << 696604;
	else if (n == 346) cout << 710210;
	else if (n == 347) cout << 723779;
	else if (n == 348) cout << 737489;
	else if (n == 349) cout << 751688;
	else if (n == 350) cout << 766274;
	else if (n == 351) cout << 780829;
	else if (n == 352) cout << 795513;
	else if (n == 353) cout << 810702;
	else if (n == 354) cout << 826301;
	else if (n == 355) cout << 841887;
	else if (n == 356) cout << 857629;
	else if (n == 357) cout << 873879;
	else if (n == 358) cout << 890597;
	else if (n == 359) cout << 907288;
	else if (n == 360) cout << 924154;
	else if (n == 361) cout << 941528;
	else if (n == 362) cout << 959393;
	else if (n == 363) cout << 977245;
	else if (n == 364) cout << 995286;
	else if (n == 365) cout << 1013885;
	else if (n == 366) cout << 1032975;
	else if (n == 367) cout << 1052093;
	else if (n == 368) cout << 1071385;
	else if (n == 369) cout << 1091281;
	else if (n == 370) cout << 1111671;
	else if (n == 371) cout << 1132103;
	else if (n == 372) cout << 1152733;
	else if (n == 373) cout << 1173985;
	else if (n == 374) cout << 1195797;
	else if (n == 375) cout << 1217619;
	else if (n == 376) cout << 1239680;
	else if (n == 377) cout << 1262371;
	else if (n == 378) cout << 1285679;
	else if (n == 379) cout << 1308981;
	else if (n == 380) cout << 1332540;
	else if (n == 381) cout << 1356777;
	else if (n == 382) cout << 1381640;
	else if (n == 383) cout << 1406549;
	else if (n == 384) cout << 1431670;
	else if (n == 385) cout << 1457552;
	else if (n == 386) cout << 1484073;
	else if (n == 387) cout << 1510684;
	else if (n == 388) cout << 1537506;
	else if (n == 389) cout << 1565116;
	else if (n == 390) cout << 1593421;
	else if (n == 391) cout << 1621798;
	else if (n == 392) cout << 1650439;
	else if (n == 393) cout << 1679840;
	else if (n == 394) cout << 1710040;
	else if (n == 395) cout << 1740299;
	else if (n == 396) cout << 1770872;
	else if (n == 397) cout << 1802228;
	else if (n == 398) cout << 1834401;
	else if (n == 399) cout << 1866678;
	else if (n == 400) cout << 1899244;
	else if (n == 401) cout << 1932673;
	else if (n == 402) cout << 1966908;
	else if (n == 403) cout << 2001335;
	else if (n == 404) cout << 2036050;
	else if (n == 405) cout << 2071698;
	else if (n == 406) cout << 2108184;
	else if (n == 407) cout << 2144840;
	else if (n == 408) cout << 2181835;
	else if (n == 409) cout << 2219749;
	else if (n == 410) cout << 2258614;
	else if (n == 411) cout << 2297613;
	else if (n == 412) cout << 2337037;
	else if (n == 413) cout << 2377417;
	else if (n == 414) cout << 2418812;
	else if (n == 415) cout << 2460348;
	else if (n == 416) cout << 2502284;
	else if (n == 417) cout << 2545262;
	else if (n == 418) cout << 2589251;
	else if (n == 419) cout << 2633488;
	else if (n == 420) cout << 2678086;
	else if (n == 421) cout << 2723846;
	else if (n == 422) cout << 2770661;
	else if (n == 423) cout << 2817745;
	else if (n == 424) cout << 2865211;
	else if (n == 425) cout << 2913832;
	else if (n == 426) cout << 2963610;
	else if (n == 427) cout << 3013638;
	else if (n == 428) cout << 3064149;
	else if (n == 429) cout << 3115809;
	else if (n == 430) cout << 3168755;
	else if (n == 431) cout << 3221964;
	else if (n == 432) cout << 3275668;
	else if (n == 433) cout << 3330581;
	else if (n == 434) cout << 3386783;
	else if (n == 435) cout << 3443347;
	else if (n == 436) cout << 3500394;
	else if (n == 437) cout << 3558776;
	else if (n == 438) cout << 3618462;
	else if (n == 439) cout << 3678591;
	else if (n == 440) cout << 3739219;
	else if (n == 441) cout << 3801227;
	else if (n == 442) cout << 3864617;
	else if (n == 443) cout << 3928426;
	else if (n == 444) cout << 3992838;
	else if (n == 445) cout << 4058644;
	else if (n == 446) cout << 4125975;
	else if (n == 447) cout << 4193706;
	else if (n == 448) cout << 4262103;
	else if (n == 449) cout << 4331969;
	else if (n == 450) cout << 4403422;
	else if (n == 451) cout << 4475328;
	else if (n == 452) cout << 4547893;
	else if (n == 453) cout << 4622058;
	else if (n == 454) cout << 4697839;
	else if (n == 455) cout << 4774178;
	else if (n == 456) cout << 4851151;
	else if (n == 457) cout << 4929820;
	else if (n == 458) cout << 5010208;
	else if (n == 459) cout << 5091182;
	else if (n == 460) cout << 5172856;
	else if (n == 461) cout << 5256256;
	else if (n == 462) cout << 5341512;
	else if (n == 463) cout << 5427359;
	else if (n == 464) cout << 5513990;
	else if (n == 465) cout << 5602366;
	else if (n == 466) cout << 5692731;
	else if (n == 467) cout << 5783763;
	else if (n == 468) cout << 5875621;
	else if (n == 469) cout << 5969326;
	else if (n == 470) cout << 6065064;
	else if (n == 471) cout << 6161565;
	else if (n == 472) cout << 6258892;
	else if (n == 473) cout << 6358179;
	else if (n == 474) cout << 6459564;
	else if (n == 475) cout << 6561813;
	else if (n == 476) cout << 6664953;
	else if (n == 477) cout << 6770155;
	else if (n == 478) cout << 6877556;
	else if (n == 479) cout << 6985831;
	else if (n == 480) cout << 7095080;
	else if (n == 481) cout << 7206442;
	else if (n == 482) cout << 7320147;
	else if (n == 483) cout << 7434771;
	else if (n == 484) cout << 7550473;
	else if (n == 485) cout << 7668411;
	else if (n == 486) cout << 7788820;
	else if (n == 487) cout << 7910189;
	else if (n == 488) cout << 8032651;
	else if (n == 489) cout << 8157462;
	else if (n == 490) cout << 8284831;
	else if (n == 491) cout << 8413281;
	else if (n == 492) cout << 8542855;
	else if (n == 493) cout << 8674944;
	else if (n == 494) cout << 8809729;
	else if (n == 495) cout << 8945676;
	else if (n == 496) cout << 9082778;
	else if (n == 497) cout << 9222463;
	else if (n == 498) cout << 9364988;
	else if (n == 499) cout << 9508754;
	else if (n == 500) cout << 9653806;
	else if (n == 501) cout << 9801500;
	else if (n == 502) cout << 9952256;
	else if (n == 503) cout << 10104316;
	else if (n == 504) cout << 10257743;
	else if (n == 505) cout << 10413890;
	else if (n == 506) cout << 10573208;
	else if (n == 507) cout << 10733939;
	else if (n == 508) cout << 10896110;
	else if (n == 509) cout << 11061190;
	else if (n == 510) cout << 11229533;
	else if (n == 511) cout << 11399469;
	else if (n == 512) cout << 11570877;
	else if (n == 513) cout << 11745355;
	else if (n == 514) cout << 11923197;
	else if (n == 515) cout << 12102719;
	else if (n == 516) cout << 12283842;
	else if (n == 517) cout << 12468149;
	else if (n == 518) cout << 12656059;
	else if (n == 519) cout << 12845678;
	else if (n == 520) cout << 13037062;
	else if (n == 521) cout << 13231723;
	else if (n == 522) cout << 13430198;
	else if (n == 523) cout << 13630435;
	else if (n == 524) cout << 13832532;
	else if (n == 525) cout << 14038103;
	else if (n == 526) cout << 14247609;
	else if (n == 527) cout << 14459090;
	else if (n == 528) cout << 14672415;
	else if (n == 529) cout << 14889455;
	else if (n == 530) cout << 15110577;
	else if (n == 531) cout << 15333859;
	else if (n == 532) cout << 15559051;
	else if (n == 533) cout << 15788106;
	else if (n == 534) cout << 16021489;
	else if (n == 535) cout << 16257099;
	else if (n == 536) cout << 16494823;
	else if (n == 537) cout << 16736430;
	else if (n == 538) cout << 16982691;
	else if (n == 539) cout << 17231268;
	else if (n == 540) cout << 17482133;
	else if (n == 541) cout << 17737038;
	else if (n == 542) cout << 17996762;
	else if (n == 543) cout << 18259008;
	else if (n == 544) cout << 18523575;
	else if (n == 545) cout << 18792461;
	else if (n == 546) cout << 19066248;
	else if (n == 547) cout << 19342858;
	else if (n == 548) cout << 19621879;
	else if (n == 549) cout << 19905482;
	else if (n == 550) cout << 20194191;
	else if (n == 551) cout << 20485801;
	else if (n == 552) cout << 20780034;
	else if (n == 553) cout << 21078917;
	else if (n == 554) cout << 21383269;
	else if (n == 555) cout << 21690564;
	else if (n == 556) cout << 22000772;
	else if (n == 557) cout << 22315811;
	else if (n == 558) cout << 22636620;
	else if (n == 559) cout << 22960518;
	else if (n == 560) cout << 23287382;
	else if (n == 561) cout << 23619378;
	else if (n == 562) cout << 23957262;
	else if (n == 563) cout << 24298589;
	else if (n == 564) cout << 24642915;
	else if (n == 565) cout << 24992740;
	else if (n == 566) cout << 25348719;
	else if (n == 567) cout << 25708352;
	else if (n == 568) cout << 26071125;
	else if (n == 569) cout << 26439509;
	else if (n == 570) cout << 26814424;
	else if (n == 571) cout << 27193076;
	else if (n == 572) cout << 27575207;
	else if (n == 573) cout << 27963063;
	else if (n == 574) cout << 28357895;
	else if (n == 575) cout << 28756665;
	else if (n == 576) cout << 29159061;
	else if (n == 577) cout << 29567444;
	else if (n == 578) cout << 29982959;
	else if (n == 579) cout << 30402778;
	else if (n == 580) cout << 30826317;
	else if (n == 581) cout << 31256272;
	else if (n == 582) cout << 31693552;
	else if (n == 583) cout << 32135502;
	else if (n == 584) cout << 32581350;
	else if (n == 585) cout << 33033850;
	else if (n == 586) cout << 33494021;
	else if (n == 587) cout << 33958959;
	else if (n == 588) cout << 34428168;
	else if (n == 589) cout << 34904200;
	else if (n == 590) cout << 35388402;
	else if (n == 591) cout << 35877518;
	else if (n == 592) cout << 36371208;
	else if (n == 593) cout << 36872015;
	else if (n == 594) cout << 37381315;
	else if (n == 595) cout << 37895834;
	else if (n == 596) cout << 38415043;
	else if (n == 597) cout << 38941834;
	else if (n == 598) cout << 39477375;
	else if (n == 599) cout << 40018569;
	else if (n == 600) cout << 40564572;
	else if (n == 601) cout << 41118515;
	else if (n == 602) cout << 41681636;
	else if (n == 603) cout << 42250661;
	else if (n == 604) cout << 42824794;
	else if (n == 605) cout << 43407106;
	else if (n == 606) cout << 43999133;
	else if (n == 607) cout << 44597265;
	else if (n == 608) cout << 45200878;
	else if (n == 609) cout << 45812892;
	else if (n == 610) cout << 46435103;
	else if (n == 611) cout << 47063812;
	else if (n == 612) cout << 47698245;
	else if (n == 613) cout << 48341510;
	else if (n == 614) cout << 48995291;
	else if (n == 615) cout << 49656026;
	else if (n == 616) cout << 50322674;
	else if (n == 617) cout << 50998599;
	else if (n == 618) cout << 51685390;
	else if (n == 619) cout << 52379573;
	else if (n == 620) cout << 53080033;
	else if (n == 621) cout << 53790160;
	else if (n == 622) cout << 54511652;
	else if (n == 623) cout << 55240790;
	else if (n == 624) cout << 55976615;
	else if (n == 625) cout << 56722410;
	else if (n == 626) cout << 57480114;
	else if (n == 627) cout << 58245804;
	else if (n == 628) cout << 59018607;
	else if (n == 629) cout << 59801874;
	else if (n == 630) cout << 60597587;
	else if (n == 631) cout << 61401680;
	else if (n == 632) cout << 62213116;
	else if (n == 633) cout << 63035515;
	else if (n == 634) cout << 63870789;
	else if (n == 635) cout << 64714957;
	else if (n == 636) cout << 65566779;
	else if (n == 637) cout << 66430128;
	else if (n == 638) cout << 67306962;
	else if (n == 639) cout << 68193147;
	else if (n == 640) cout << 69087304;
	else if (n == 641) cout << 69993376;
	else if (n == 642) cout << 70913541;
	else if (n == 643) cout << 71843474;
	else if (n == 644) cout << 72781898;
	else if (n == 645) cout << 73732659;
	else if (n == 646) cout << 74698257;
	else if (n == 647) cout << 75674119;
	else if (n == 648) cout << 76658893;
	else if (n == 649) cout << 77656445;
	else if (n == 650) cout << 78669362;
	else if (n == 651) cout << 79693081;
	else if (n == 652) cout << 80726131;
	else if (n == 653) cout << 81772616;
	else if (n == 654) cout << 82835012;
	else if (n == 655) cout << 83908916;
	else if (n == 656) cout << 84992556;
	else if (n == 657) cout << 86090212;
	else if (n == 658) cout << 87204345;
	else if (n == 659) cout << 88330485;
	else if (n == 660) cout << 89466924;
	else if (n == 661) cout << 90617927;
	else if (n == 662) cout << 91786245;
	else if (n == 663) cout << 92967022;
	else if (n == 664) cout << 94158757;
	else if (n == 665) cout << 95365564;
	else if (n == 666) cout << 96590480;
	else if (n == 667) cout << 97828338;
	else if (n == 668) cout << 99077637;
	else if (n == 669) cout << 100342758;
	else if (n == 670) cout << 101626642;
	else if (n == 671) cout << 102924276;
	else if (n == 672) cout << 104233689;
	else if (n == 673) cout << 105559752;
	else if (n == 674) cout << 106905263;
	else if (n == 675) cout << 108265297;
	else if (n == 676) cout << 109637563;
	else if (n == 677) cout << 111027158;
	else if (n == 678) cout << 112437124;
	else if (n == 679) cout << 113862179;
	else if (n == 680) cout << 115300256;
	else if (n == 681) cout << 116756094;
	else if (n == 682) cout << 118233360;
	else if (n == 683) cout << 119726327;
	else if (n == 684) cout << 121233054;
	else if (n == 685) cout << 122758214;
	else if (n == 686) cout << 124305620;
	else if (n == 687) cout << 125869592;
	else if (n == 688) cout << 127447802;
	else if (n == 689) cout << 129045403;
	else if (n == 690) cout << 130665851;
    return 0;
}

Tips 数据水的很(1<=n<=690)