1 0 2 1 3 1 4 7 5 1 6 19 7 1 8 35 9 13 10 37 11 1 12 119 13 1 14 63 15 43 16 155 17 1 18 208 19 1 20 245 21 69 22 139 23 1 24 575 25 31 26 189 27 130 28 427 29 1 30 661 31 1 32 651 33 145 34 313 35 87 36 1274 37 1 38 387 39 195 40 1205 41 1 42 1155 43 1 44 959 45 520 46 559 47 1 48 2511 49 57 50 992 51 319 52 1309 53 1 54 1990 55 163 56 2115 57 393 58 877 59 1 60 4025 61 1 62 999 63 858 64 2667 65 213 66 2599 67 1 68 2177 69 565 70 2289 71 1 72 6110 73 1 74 1413 75 1178 76 2695 77 189 78 3549 79 1 80 5301 81 1210 82 1729 83 1 84 7119 85 337 86 1899 87 883 88 4775 89 1 90 7150 91 239 92 3899 93 1005 94 2263 95 411 96 10479 97 1 98 3192 99 1846 100 6510 101 1 102 5905 103 1 104 6525 105 2811 106 2869 107 1 108 12110 109 1 110 5101 111 1419 112 9331 113 1 114 7311 115 583 116 6125 117 2496 118 3547 119 363 120 19265 121 133 122 3789 123 1735 124 6979 125 806 126 12558 127 1 128 10795 129 1905 130 6951 131 1 132 16163 133 437 134 4563 135 5110 136 10865 137 1 138 10579 139 1 140 14805 141 2269 142 5119 143 315 144 26598 145 901 146 5409 147 3534 148 9877 149 1 150 17546 151 1 152 13455 153 4108 154 8715 155 1023 156 22113 157 1 158 6327 159 2875 160 22197 161 609 162 18271 163 1 164 12089 165 6079 166 6979 167 1 168 34215 169 183 170 11539 171 5070 172 13279 173 1 174 16621 175 2542 176 21111 177 3553 178 8017 179 1 180 42770 181 1 182 11865 183 3795 184 19475 185 1437 186 18939 187 439 188 15827 189 8490 190 14277 191 1 192 42799 193 1 194 9513 195 8229 196 21546 197 1 198 28366 199 1 200 31930 201 4569 202 10309 203 927 204 36869 205 1753 206 10719 207 7306 208 28861 209 513 210 39837 211 1 212 20069 213 5125 214 11563 215 1923 216 57950 217 1049 218 11997 219 5415 220 33425 221 489 222 26805 223 1 224 39123 225 14105 226 12889 227 1 228 45675 229 1 230 20641 231 9849 232 30605 233 1 234 38766 235 2287 236 24815 237 6333 238 19677 239 1 240 83793 241 1 242 17024 243 11011 244 26509 245 4560 246 32809 247 563 248 34875 249 6985 250 25142 251 1 252 75894 253 685 254 16263 255 13561 256 43435 257 1 258 36039 259 1463 260 45675 261 11440 262 17299 263 1 264 77915 265 2893 266 24339 267 8023 268 31927 269 1 270 68170 271 1 272 48081 273 13299 274 18913 275 4898 276 66143 277 1 278 19467 279 13026 280 72285 281 1 282 42955 283 1 284 35819 285 16743 286 26229 287 1779 288 110838 289 307 290 32407 291 9519 292 37849 293 1 294 58254 295 3571 296 49365 297 18370 298 22357 299 735 300 106330 301 1949 302 22959 303 10315 304 59551 305 3813 306 64558 307 1 308 58359 309 10725 310 36921 311 1 312 106665 313 1 314 24813 315 33150 316 44275 317 1 318 54469 319 1003 320 90805 321 11569 322 35175 323 687 324 110957 325 6448 326 26739 327 12003 328 60425 329 2313 330 90073 331 1 332 48839 333 18408 334 28063 335 4587 336 149079 337 1 338 32208 339 12895 340 76055 341 1125 342 79950 343 2850 344 66375 345 24139 346 30109 347 1 348 103985 349 1 350 61194 351 24870 352 88599 353 1 354 67351 355 5143 356 56105 357 21855 358 32227 359 1 360 203450 361 381 362 32949 363 17822 364 79709 365 5433 366 71949 367 1 368 86211 369 22516 370 52239 371 2919 372 118503 373 1 374 43465 375 29978 376 79115 377 1053 378 119910 379 1 380 94185 381 16269 382 36679 383 1 384 172975 385 13251 386 37449 387 24726 388 66577 389 1 390 123123 391 859 392 106590 393 17305 394 39013 395 6351 396 172718 397 1 398 39807 399 26961 400 140306 401 1 402 86655 403 1175 404 72149 405 47311 406 55209 407 1539 408 177965 409 1 410 63931 411 18919 412 75019 413 3597 414 115726 415 7003 416 121149 417 19473 418 53751 419 1 420 239505 421 1 422 44739 423 29458 424 100325 425 10292 426 97219 427 3839 428 80927 429 28119 430 70221 431 1 432 252030 433 1 434 62895 435 37813 436 83965 437 933 438 102729 439 1 440 163865 441 43719 442 59115 443 1 444 167769 445 8041 446 49959 447 22363 448 160147 449 1 450 189410 451 1855 452 90209 453 22965 454 51763 455 17601 456 220515 457 1 458 52677 459 40990 460 136325 461 1 462 157647 463 1 464 135501 465 43059 466 54529 467 1 468 236418 469 4613 470 83689 471 24819 472 124055 473 2025 474 120171 475 12586 476 132657 477 37336 478 57367 479 1 480 349041 481 1589 482 58329 483 38829 484 117306 485 9537 486 165529 487 1 488 132525 489 26745 490 115710 491 1 492 205373 493 1177 494 73101 495 72670 496 154411 497 5169 498 132559 499 1 500 164710 501 28069 502 63259 503 1 504 362310 505 10333 506 77659 507 33306 508 113827 509 1 510 205087 511 5459 512 174251 513 50610 514 66313 515 10743 516 225603 517 2389 518 88977 519 30115 520 224115 521 1 522 181870 523 1 524 121079 525 76446 526 69439 527 1299 528 339915 529 553 530 106111 531 46150 532 164255 533 1905 534 152281 535 11587 536 159615 537 32233 538 72637 539 10374 540 405650 541 1 542 73719 543 32955 544 201873 545 12021 546 215397 547 1 548 132377 549 49296 550 136586 551 1251 552 319415 553 6377 554 77013 555 60861 556 136255 557 1 558 207246 559 2075 560 317037 561 46099 562 79249 563 1 564 268919 565 12913 566 80379 567 78771 568 179075 569 1 570 254001 571 1 572 179193 573 36685 574 108885 575 17918 576 452374 577 1 578 90872 579 37455 580 214235 581 7029 582 180705 583 2995 584 189225 585 98670 586 86149 587 1 588 358302 589 1373 590 131197 591 39019 592 218581 593 1 594 271150 595 28389 596 156485 597 39813 598 105609 599 1 600 508090 601 1 602 119595 603 59358 604 160699 605 20216 606 195829 607 1 608 250047 609 60771 610 140151 611 2439 612 394394 613 1 614 94563 615 74449 616 288015 617 1 618 203619 619 1 620 244125 621 72970 622 97039 623 8067 624 465465 625 20306 626 98289 627 56829 628 173677 629 1713 630 428610 631 1 632 221355 633 44745 634 100813 635 16287 636 341033 637 13224 638 121861 639 66586 640 367285 641 1 642 219655 643 1 644 237699 645 81759 646 121089 647 1 648 530585 649 3673 650 186186 651 69189 652 187159 653 1 654 227901 655 17323 656 267561 657 70356 658 142527 659 1 660 545405 661 1 662 109899 663 62049 664 244175 665 34827 666 293358 667 1423 668 196427 669 49965 670 168789 671 3915 672 621495 673 1 674 113913 675 138260 676 222894 677 1 678 244849 679 9563 680 373535 681 51769 682 138819 683 1 684 488670 685 18937 686 157150 687 52683 688 293911 689 3045 690 367693 691 1 692 210749 693 120666 694 120763 695 19491 696 502265 697 2029 698 122157 699 54535 700 392770 701 1 702 370650 703 1787 704 362839 705 97411 706 124969 707 10359 708 421715 709 1 710 189361 711 82290 712 280505 713 1545 714 358617 715 33789 716 225575 717 57373 718 129247 719 1 720 882570 721 10769 722 140208 723 58335 724 230629 725 27776 726 317870 727 1 728 393765 729 99463 730 200091 731 2199 732 450513 733 1 734 135063 735 143070 736 362019 737 4689 738 359086 739 1 740 345555 741 76479 742 180705 743 1 744 572415 745 22381 746 139509 747 90766 748 298109 749 11613 750 443846 751 1 752 350331 753 63265 754 165711 755 22983 756 720510 757 1 758 144027 759 81769 760 462705 761 1 762 308955 763 12047 764 256739 765 163150 766 147079 767 3723 768 695471 769 1 770 314517 771 66319 772 262129 773 1 774 394446 775 31558 776 332865 777 97755 778 151717 779 2103 780 746655 781 5245 782 174925 783 114310 784 470022 785 24837 786 328639 787 1 788 273077 789 69445 790 234057 791 12939 792 826670 793 3965 794 158013 795 123469 796 278635 797 1 798 444087 799 2563 800 587202 801 104260 802 161209 803 5535 804 542619 805 49791 806 188769 807 72643 808 360725 809 1 810 625207 811 1 812 373485 813 73725 814 196365 815 26763 816 776829 817 2273 818 167697 819 163566 820 422975 821 1 822 359305 823 1 824 375075 825 165974 826 223419 827 1 828 707798 829 1 830 258181 831 77019 832 496189 833 20292 834 369831 835 28087 836 369075 837 130170 838 175987 839 1 840 1141305 841 871 842 177669 843 79255 844 313159 845 36600 846 470158 847 23674 848 444261 849 80385 850 309194 851 1959 852 608783 853 1 854 238665 855 201630 856 404615 857 1 858 485121 859 1 860 464625 861 119559 862 186199 863 1 864 1049790 865 30133 866 187929 867 92714 868 425579 869 6453 870 577891 871 4739 872 419805 873 123708 874 216291 875 65442 876 643293 877 1 878 193167 879 86155 880 719913 881 1 882 632814 883 1 884 406959 885 152623 886 196699 887 1 888 810465 889 16313 890 296587 891 170731 892 349699 893 2637 894 424741 895 32251 896 647955 897 110019 898 202057 899 1863 900 1128400 901 3169 902 240289 903 131289 904 451025 905 32973 906 436179 907 1 908 362327 909 134056 910 428967 911 1 912 962643 913 7105 914 209313 915 163029 916 368725 917 17349 918 617410 919 1 920 669965 921 94569 922 212989 923 5295 924 965643 925 44392 926 214839 927 139386 928 569037 929 1 930 658533 931 24510 932 381689 933 97045 934 218563 935 54001 936 1132170 937 1 938 287427 939 98295 940 553805 941 1 942 471405 943 2275 944 549351 945 323670 946 263919 947 1 948 752535 949 5585 950 382602 951 100819 952 656025 953 1 954 596206 955 36703 956 401555 957 127879 958 229927 959 18963 960 1424305 961 993 962 267015 963 150358 964 408289 965 37473 966 642747 967 1 968 583870 969 125211 970 351939 971 1 972 1004549 973 19517 974 237663 975 224874 976 586861 977 1 978 507999 979 8143 980 746130 981 156000 982 241579 983 1 984 992165 985 39037 986 274459 987 156405 988 503825 989 2445 990 972010 991 1 992 648459 993 109905 994 322455 995 39831 996 830123 997 1 998 249507 999 183990 1000 807430