1 1 2 1 3 2 4 5 5 11 6 4 7 3 8 18 9 26 10 35 11 48 12 15 13 76 14 64 15 97 16 135 17 29 18 6 19 175 20 98 21 212 22 240 23 260 24 73 25 22 26 316 27 41 28 232 29 7 30 165 31 424 32 472 33 399 34 519 35 214 36 353 37 606 38 27 39 660 40 100 41 787 42 845 43 924 44 963 45 376 46 156 47 1095 48 766 49 356 50 621 51 1206 52 32 53 501 54 1292 55 1409 56 1169 57 1464 58 902 59 259 60 1463 61 56 62 103 63 1760 64 1917 65 1893 66 980 67 1715 68 459 69 1653 70 1812 71 219 72 19 73 2171 74 1555 75 2529 76 30 77 2742 78 690 79 2939 80 2677 81 3178 82 2437 83 3448 84 2200 85 278 86 3014 87 1168 88 2923 89 2714 90 3320 91 3930 92 1914 93 3652 94 4117 95 130 96 4489 97 403 98 713 99 4589 100 4021 101 185 102 1426 103 4570 104 4826 105 5031 106 5313 107 180 108 1388 109 2558 110 5460 111 3221 112 5908 113 2216 114 6229 115 5204 116 1092 117 4353 118 4211 119 6206 120 2271 121 6595 122 5974 123 605 124 7100 125 2413 126 5058 127 7521 128 7343 129 7462 130 7067 131 8195 132 4086 133 269 134 7967 135 801 136 783 137 348 138 53 139 8655 140 8830 141 5699 142 9475 143 1592 144 9740 145 9992 146 5627 147 7792 148 10474 149 9483 150 4135 151 20 152 11078 153 3229 154 436 155 9298 156 9892 157 2100 158 11515 159 12101 160 10449 161 11954 162 12671 163 683 164 13050 165 7887 166 12561 167 1117 168 8984 169 2170 170 13836 171 11688 172 12083 173 13486 174 1987 175 14687 176 8787 177 454 178 15135 179 7603 180 825 181 6569 182 3199 183 10555 184 14814 185 15645 186 16288 187 16762 188 5929 189 17071 190 2557 191 17612 192 18323 193 651 194 14038 195 16616 196 8226 197 312 198 11082 199 129 200 18993 201 17865 202 18695 203 19606 204 20008 205 17972 206 19781 207 20729 208 21782 209 3321 210 21471 211 22116 212 20977 213 22686 214 2988 215 8025 216 838 217 23580 218 114 219 22619 220 23129 221 22997 222 591 223 7158 224 2498 225 8982 226 20908 227 9788 228 16727 229 25668 230 25955 231 26389 232 26815 233 14351 234 27267 235 28402 236 1993 237 3794 238 6326 239 22554 240 17688 241 4877 242 25152 243 23854 244 29486 245 215 246 28650 247 15889 248 30538 249 25952 250 31224 251 30261 252 31752 253 32123 254 18529 255 26271 256 772 257 22621 258 8 259 27230 260 34607 261 28151 262 2525 263 32022 264 7144 265 16953 266 14045 267 1972 268 31220 269 34689 270 32998 271 4392 272 1823 273 8169 274 34435 275 36253 276 11169 277 13362 278 37684 279 5444 280 24345 281 32722 282 39105 283 27004 284 37478 285 39863 286 13126 287 18820 288 15720 289 36766 290 41549 291 32919 292 41056 293 39196 294 37801 295 40465 296 8121 297 17975 298 2022 299 42531 300 30541 301 43179 302 39038 303 46196 304 1283 305 46951 306 44091 307 47995 308 47234 309 12757 310 584 311 22464 312 49239 313 28065 314 49105 315 36946 316 526 317 10426 318 29866 319 32427 320 6032 321 18460 322 10868 323 51786 324 44713 325 48312 326 50826 327 267 328 38471 329 49604 330 49190 331 51887 332 45067 333 54210 334 52840 335 2556 336 23397 337 55377 338 56498 339 3315 340 57263 341 55255 342 40464 343 56852 344 41616 345 17179 346 58729 347 36817 348 54322 349 2457 350 53161 351 59467 352 15925 353 60564 354 6737 355 12411 356 61650 357 54926 358 62123 359 36431 360 13405 361 64324 362 64925 363 16625 364 161 365 19112 366 61628 367 33721 368 64676 369 7709 370 14968 371 66103 372 67291 373 2804 374 68491 375 847 376 68262 377 51977 378 64519 379 69367 380 71269 381 67818 382 25378 383 73681 384 71462 385 8466 386 72248 387 62334 388 26058 389 9736 390 74065 391 75354 392 76733 393 77277 394 78304 395 71016 396 38425 397 79919 398 80565 399 81133 400 54052 401 5445 402 1811 403 9733 404 3437 405 78534 406 82473 407 6298 408 81359 409 2430 410 83946 411 82794 412 28256 413 31914 414 76676 415 56690 416 41897 417 86084 418 87570 419 585 420 3358 421 86635 422 78490 423 90214 424 89825 425 48097 426 57586 427 67201 428 23428 429 85925 430 56189 431 5749 432 870 433 93187 434 91368 435 22550 436 37711 437 1014 438 94525 439 96287 440 41535 441 89507 442 83124 443 90575 444 98195 445 100185 446 17630 447 17424 448 97291 449 94776 450 101518 451 84052 452 99382 453 14059 454 104369 455 64791 456 105794 457 104022 458 5892 459 2893 460 51684 461 106527 462 108215 463 51044 464 105665 465 31404 466 16447 467 104619 468 42733 469 110012 470 95631 471 72065 472 109033 473 368 474 85983 475 113314 476 101696 477 114160 478 1745 479 115943 480 3821 481 105226 482 58624 483 118238 484 119505 485 107117 486 118767 487 44182 488 40635 489 14562 490 120733 491 50006 492 91528 493 124381 494 10829 495 14519 496 77768 497 123336 498 120684 499 81345 500 534 501 9941 502 38277 503 104536 504 115476 505 72398 506 99185 507 109221 508 25887 509 1499 510 13852 511 124406 512 125950 513 99901 514 101510 515 4898 516 639 517 113304 518 24870 519 80509 520 109496 521 87680 522 6170 523 129453 524 98661 525 134553 526 52009 527 65613 528 25839 529 69318 530 133226 531 118485 532 139367 533 67670 534 32779 535 137628 536 139168 537 616 538 83888 539 45232 540 39741 541 132362 542 59016 543 123907 544 131715 545 58019 546 122358 547 116047 548 129120 549 142243 550 145014 551 138678 552 143821 553 149100 554 11711 555 148285 556 152035 557 150719 558 153986 559 91934 560 153372 561 140866 562 149495 563 157049 564 155009 565 158494 566 147616 567 159813 568 5038 569 55046 570 162620 571 1314 572 161661 573 164583 574 165403 575 28765 576 166650 577 168143 578 169454 579 155380 580 95986 581 168788 582 170592 583 166872 584 22548 585 13107 586 150312 587 2735 588 10397 589 36359 590 171161 591 177226 592 5793 593 176110 594 149529 595 159088 596 175740 597 165625 598 160802 599 114918 600 44501 601 32159 602 179517 603 152628 604 178831 605 185265 606 123259 607 176662 608 143754 609 26770 610 8600 611 184859 612 141798 613 187779 614 144313 615 190309 616 184234 617 193574 618 52832 619 43125 620 62690 621 192576 622 187984 623 196264 624 197675 625 199256 626 83914 627 37533 628 201603 629 102841 630 206032 631 198097 632 208834 633 91346 634 129243 635 97627 636 196807 637 52111 638 204582 639 56027 640 133105 641 202999 642 206493 643 99812 644 826 645 214533 646 198455 647 207971 648 210656 649 187626 650 218111 651 217630 652 220095 653 219058 654 225042 655 41988 656 146399 657 204602 658 39 659 4692 660 155828 661 227411 662 118573 663 224488 664 223949 665 68167 666 23765 667 213286 668 18224 669 2199 670 12217 671 206400 672 2288 673 28458 674 32062 675 110622 676 221393 677 224886 678 10255 679 16940 680 235356 681 234989 682 235729 683 14526 684 97752 685 240643 686 232592 687 199366 688 229708 689 244428 690 241059 691 192272 692 209640 693 80076 694 244904 695 133827 696 545 697 146291 698 247609 699 249821 700 250955 701 5018 702 3544 703 89543 704 255624 705 84206 706 46786 707 44447 708 258881 709 254652 710 247906 711 109081 712 243430 713 241535 714 48467 715 183807 716 28794 717 217013 718 263880 719 1802 720 262403 721 267334 722 264830 723 240167 724 175389 725 11542 726 31681 727 261322 728 269113 729 271983 730 273101 731 212167 732 31379 733 380 734 270882 735 266744 736 183035 737 251939 738 141394 739 274050 740 164947 741 23683 742 158294 743 281522 744 224 745 283469 746 251695 747 271004 748 279069 749 282547 750 237773 751 85646 752 287818 753 291297 754 284716 755 294492 756 4480 757 20426 758 114257 759 192371 760 2905 761 288878 762 296136 763 293241 764 77223 765 279408 766 264998 767 301502 768 253925 769 2513 770 307063 771 91104 772 78125 773 309749 774 231886 775 6661 776 316204 777 312809 778 303765 779 261906 780 75622 781 37492 782 294111 783 11835 784 39527 785 3522 786 318417 787 286928 788 176452 789 312432 790 5786 791 321066 792 193216 793 92680 794 318671 795 300511 796 313021 797 189577 798 322110 799 319703 800 114673 801 238598 802 208387 803 331377 804 69135 805 82783 806 126021 807 289294 808 328017 809 337621 810 136676 811 167238 812 343665 813 327562 814 331115 815 338567 816 335789 817 31764 818 2778 819 124099 820 284539 821 162961 822 14612 823 344332 824 226358 825 346924 826 309406 827 146716 828 353242 829 357115 830 344711 831 47298 832 334488 833 249007 834 50985 835 70726 836 262662 837 362471 838 361259 839 179816 840 4742 841 275367 842 358794 843 332096 844 34381 845 357358 846 352892 847 362050 848 367668 849 365724 850 132969 851 164457 852 326942 853 369505 854 27070 855 371152 856 144284 857 30812 858 381310 859 10475 860 383714 861 125062 862 80413 863 364523 864 13492 865 211488 866 360050 867 933 868 387669 869 124387 870 4939 871 395332 872 24971 873 394571 874 280 875 385093 876 81284 877 403761 878 205731 879 403089 880 392120 881 63503 882 21419 883 399890 884 404898 885 44162 886 376502 887 411851 888 383251 889 180353 890 58317 891 416428 892 402007 893 414838 894 273147 895 376845 896 398038 897 424285 898 237136 899 430419 900 14568 901 361601 902 10529 903 415817 904 422222 905 434930 906 429128 907 122560 908 36883 909 323618 910 370053 911 70815 912 9906 913 407546 914 396027 915 111623 916 441722 917 437732 918 449150 919 3486 920 431398 921 8926 922 46010 923 94081 924 260168 925 7720 926 394946 927 315433 928 435553 929 31619 930 433986 931 285645 932 146402 933 421099 934 454993 935 451976 936 271536 937 442783 938 276 939 3483 940 466283 941 432895 942 341673 943 161971 944 416025 945 398642 946 15319 947 450947 948 462067 949 264634 950 303447 951 380130 952 179970 953 445957 954 245029 955 8104 956 23122 957 457406 958 453033 959 472317 960 468785 961 474330 962 480849 963 1212 964 471021 965 448920 966 414777 967 484116 968 482404 969 479451 970 486364 971 446361 972 382113 973 149970 974 476950 975 495027 976 494594 977 490890 978 500059 979 479998 980 375019 981 114183 982 504734 983 499526 984 509528 985 10431 986 515918 987 166850 988 520135 989 512927 990 503539 991 518110 992 88774 993 201593 994 220305 995 530206 996 519561 997 427434 998 49410 999 133853 1000 364026