1 0 2 1 3 3 4 4 5 7 6 12 7 12 8 19 9 22 10 29 11 25 12 40 13 29 14 48 15 59 16 85 17 42 18 83 19 53 20 93 21 99 22 96 23 64 24 175 25 144 26 113 27 159 28 161 29 97 30 235 31 100 32 297 33 187 34 165 35 231 36 274 37 111 38 200 39 224 40 386 41 156 42 398 43 149 44 303 45 425 46 248 47 152 48 733 49 450 50 513 51 332 52 359 53 181 54 572 55 448 56 648 57 384 58 361 59 221 60 786 61 225 62 384 63 691 64 977 65 540 66 738 67 239 68 541 69 490 70 912 71 332 72 1123 73 264 74 421 75 997 76 625 77 725 78 881 79 344 80 1570 81 1159 82 585 83 319 84 1364 85 810 86 552 87 695 88 1208 89 426 90 1634 91 876 92 815 93 759 94 592 95 937 96 2617 97 406 98 1635 99 1309 100 1611 101 431 102 1303 103 420 104 1441 105 1869 106 673 107 401 108 1792 109 525 110 1746 111 824 112 2640 113 504 114 1512 115 1163 116 1109 117 1565 118 824 119 1363 120 3211 121 2302 122 841 123 1148 124 1265 125 1839 126 2695 127 602 128 3233 129 1044 130 2087 131 659 132 2466 133 1522 134 884 135 3107 136 2162 137 564 138 1948 139 701 140 3089 141 1186 142 1232 143 1674 144 4549 145 1633 146 1009 147 3281 148 1327 149 667 150 3833 151 744 152 2470 153 2403 154 2829 155 1789 156 2963 157 617 158 1296 159 1295 160 5492 161 1970 162 4145 163 647 164 1861 165 3461 166 1188 167 772 168 5503 169 3832 170 3133 171 2724 172 1697 173 637 174 2669 175 4004 176 4814 177 1579 178 1565 179 887 180 5476 181 1107 182 3401 183 1640 184 3222 185 2066 186 3016 187 2490 188 1999 189 4893 190 3606 191 996 192 8689 193 784 194 1557 195 4134 196 5433 197 1045 198 5033 199 1162 200 6296 201 1668 202 1581 203 2616 204 4527 205 2650 206 1568 207 3448 208 5781 209 3329 210 7374 211 1139 212 2069 213 2386 214 1496 215 2494 216 7039 217 3118 218 1913 219 2021 220 5729 221 2946 222 3197 223 1108 224 9454 225 7269 226 1897 227 907 228 5045 229 1175 230 4551 231 5739 232 4339 233 1182 234 6041 235 2803 236 2591 237 2547 238 5344 239 1544 240 12981 241 1410 242 8091 243 7482 244 2647 245 7829 246 4437 247 3426 248 5002 249 2275 250 6393 251 1541 252 9298 253 3661 254 2260 255 6303 256 9537 257 1084 258 4082 259 3315 260 6886 261 4710 262 2396 263 1244 264 9931 265 3208 266 5837 267 3032 268 2713 269 1423 270 11651 271 1682 272 8671 273 6852 274 2105 275 8395 276 6725 277 1107 278 2552 279 5241 280 12332 281 1656 282 4732 283 1049 284 3935 285 7065 286 6437 287 4446 288 16393 289 9312 290 6195 291 3161 292 3319 293 1357 294 12653 295 3786 296 5236 297 9481 298 2421 299 4330 300 12966 301 4025 302 2728 303 3035 304 9807 305 3952 306 9217 307 1901 308 9609 309 3027 310 6934 311 1840 312 11917 313 1484 314 2297 315 13711 316 4241 317 1177 318 4975 319 5805 320 18006 321 2863 322 7723 323 5699 324 13150 325 9053 326 2372 327 3668 328 7297 329 4904 330 13648 331 1829 332 3735 333 6032 334 2912 335 3989 336 22205 337 2028 338 13449 339 3776 340 10515 341 6437 342 10448 343 8280 344 6635 345 9224 346 2353 347 1397 348 8811 349 2145 350 15260 351 11444 352 16906 353 1788 354 6182 355 5785 356 4893 357 10983 358 3260 359 2156 360 21871 361 14958 362 3997 363 15617 364 11500 365 5045 366 6331 367 1712 368 12815 369 7727 370 7906 371 5115 372 10502 373 1979 374 9582 375 12107 376 7926 377 7364 378 18654 379 2627 380 11649 381 4443 382 3776 383 1724 384 28897 385 14206 386 3073 387 7121 388 5247 389 2167 390 16326 391 6816 392 21218 393 4531 394 3769 395 5885 396 17146 397 2061 398 4244 399 11677 400 24916 401 2256 402 6518 403 6543 404 4861 405 22427 406 10055 407 6422 408 18184 409 2436 410 10158 411 4124 412 4993 413 6135 414 13398 415 5458 416 20136 417 4836 418 12647 419 3191 420 25996 421 2655 422 4076 423 8416 424 8082 425 13725 426 9318 427 6369 428 4703 429 12952 430 9528 431 2768 432 27901 433 2808 434 12127 435 12214 436 5879 437 7430 438 7877 439 2648 440 22712 441 23343 442 11428 443 2365 444 10769 445 7313 446 4192 447 4595 448 32364 449 3374 450 27548 451 9437 452 6197 453 5211 454 3372 455 16776 456 20014 457 2192 458 4269 459 17502 460 15527 461 3321 462 22747 463 3068 464 17165 465 13985 466 4325 467 2447 468 20521 469 6424 470 11033 471 4472 472 10132 473 7610 474 10020 475 17886 476 18633 477 9380 478 5744 479 2876 480 47081 481 7654 482 5301 483 16054 484 25389 485 7411 486 26042 487 2424 488 10374 489 4452 490 29971 491 3047 492 15129 493 8835 494 13155 495 25929 496 19896 497 9664 498 8908 499 2563 500 19381 501 5746 502 5568 503 3104 504 37003 505 6992 506 14156 507 25913 508 7401 509 2857 510 24837 511 8512 512 31361 513 20071 514 4169 515 7089 516 13506 517 8865 518 12803 519 4511 520 27283 521 3654 522 17861 523 2447 524 7367 525 30783 526 4688 527 11215 528 39735 529 25858 530 12161 531 11097 532 19499 533 12129 534 11621 535 7368 536 10584 537 6247 538 5101 539 23787 540 38026 541 3321 542 6140 543 7664 544 31166 545 9140 546 27102 547 3119 548 6693 549 11434 550 31754 551 12403 552 26780 553 10162 554 4117 555 15729 556 7873 557 2611 558 20307 559 11631 560 49300 561 19513 562 6113 563 2279 564 16752 565 8561 566 3872 567 35731 568 15355 569 3480 570 27796 571 4169 572 21506 573 7558 574 17171 575 19580 576 54673 577 3504 578 33601 579 6389 580 19940 581 8842 582 12353 583 9794 584 13108 585 30783 586 4913 587 3097 588 44990 589 13586 590 14608 591 7163 592 20843 593 3858 594 36114 595 27000 596 7309 597 8151 598 16839 599 4488 600 51571 601 4456 602 15382 603 11366 604 8529 605 38047 606 11613 607 3124 608 33950 609 20148 610 15072 611 10511 612 31682 613 3231 614 6824 615 20312 616 38206 617 3804 618 11870 619 3269 620 23415 621 24991 622 6776 623 12106 624 47612 625 29744 626 5593 627 25227 628 7223 629 12903 630 53627 631 4782 632 16646 633 7572 634 4345 635 10821 636 16455 637 32114 638 21961 639 17052 640 59484 641 3708 642 11224 643 3455 644 27174 645 18581 646 21692 647 4316 648 50923 649 14150 650 34306 651 24963 652 7225 653 2437 654 14007 655 10642 656 28915 657 14979 658 19340 659 5099 660 47488 661 4275 662 6536 663 23151 664 14595 665 29025 666 23105 667 12822 668 9599 669 8343 670 15210 671 14718 672 82041 673 4144 674 7617 675 54457 676 42147 677 3103 678 14635 679 13105 680 41530 681 6451 682 24501 683 4517 684 34880 685 9460 686 29264 687 8180 688 26270 689 11627 690 36499 691 3899 692 7205 693 42457 694 5192 695 11194 696 34953 697 15181 698 7689 699 8360 700 51555 701 5891 702 43193 703 14885 704 55490 705 22737 706 6761 707 11275 708 20814 709 3711 710 22310 711 17105 712 19024 713 15344 714 43608 715 32312 716 10247 717 11362 718 8048 719 5072 720 87421 721 11870 722 52051 723 10685 724 12319 725 30688 726 59175 727 5262 728 45545 729 43288 730 19453 731 13544 732 21368 733 2969 734 6432 735 61197 736 45913 737 12155 738 29523 739 4625 740 26082 741 26104 742 19620 743 4540 744 41831 745 10848 746 7173 747 15992 748 32623 749 11833 750 45663 751 4856 752 31498 753 10567 754 27839 755 12318 756 62668 757 4779 758 9356 759 28894 760 46090 761 4656 762 17450 763 14557 764 12719 765 47463 766 6768 767 13970 768 85441 769 6308 770 55575 771 8492 772 10759 773 3637 774 27261 775 33936 776 20737 777 25914 778 7741 779 20458 780 56875 781 20511 782 26482 783 33411 784 84106 785 10776 786 17526 787 2939 788 11429 789 9250 790 22654 791 14868 792 68185 793 14533 794 7561 795 23919 796 13369 797 4597 798 46115 799 17825 800 87986 801 21397 802 8441 803 15847 804 21553 805 39343 806 25305 807 9611 808 18884 809 5412 810 84362 811 6365 812 33432 813 11823 814 24594 815 11499 816 72684 817 15754 818 8969 819 50806 820 33704 821 4347 822 15907 823 3480 824 19528 825 63229 826 23669 827 5441 828 46954 829 5385 830 21065 831 8012 832 66269 833 47079 834 18720 835 13703 836 41717 837 36747 838 11444 839 6476 840 103951 841 65736 842 9661 843 12044 844 12169 845 63073 846 32865 847 61382 848 31941 849 7284 850 52265 851 16832 852 31842 853 4539 854 24533 855 53271 856 18390 857 5424 858 50897 859 6353 860 30668 861 35162 862 10304 863 5180 864 98425 865 10533 866 10441 867 67189 868 42501 869 20941 870 47772 871 14458 872 22786 873 21924 874 28584 875 46245 876 27497 877 3557 878 9768 879 9311 880 90672 881 8064 882 89436 883 6827 884 39000 885 29049 886 8568 887 4312 888 42973 889 18744 890 27752 891 69153 892 14001 893 17916 894 17489 895 15796 896 111910 897 34559 898 12389 899 24808 900 92896 901 20677 902 35939 903 30753 904 24325 905 18902 906 20248 907 3389 908 10599 909 20107 910 66091 911 8144 912 80156 913 16973 914 8257 915 30033 916 13119 917 17173 918 66234 919 7370 920 61410 921 12840 922 11801 923 26220 924 81036 925 35132 926 11144 927 20419 928 59360 929 6612 930 55242 931 49542 932 13485 933 13162 934 8972 935 48747 936 81532 937 7140 938 24544 939 11189 940 38588 941 4989 942 17225 943 21844 944 40002 945 102399 946 28925 947 5107 948 34850 949 18859 950 67234 951 8327 952 74050 953 6882 954 35435 955 17509 956 18959 957 42776 958 11024 959 15947 960 157521 961 76950 962 29312 963 21926 964 17727 965 15105 966 63470 967 7072 968 97340 969 43171 970 28734 971 6089 972 79300 973 18092 974 8888 975 68620 976 41136 977 4608 978 17318 979 25853 980 103097 981 26418 982 10916 983 4784 984 60211 985 17296 986 33614 987 40709 988 43306 989 26601 990 101333 991 8626 992 71416 993 12132 994 37498 995 19589 996 30021 997 4047 998 9324 999 46406 1000 74146