1 0 2 0 3 0 4 1 5 1 6 4 7 3 8 11 9 4 10 21 11 10 12 30 13 15 14 51 15 14 16 71 17 28 18 86 19 36 20 119 21 36 22 150 23 55 24 178 25 59 26 219 27 68 28 269 29 91 30 278 31 105 32 367 33 110 34 396 35 116 36 469 37 153 38 504 39 162 40 587 41 190 42 608 43 210 44 752 45 199 46 759 47 253 48 906 49 261 50 879 51 296 52 1085 53 325 54 1068 55 322 56 1249 57 378 58 1239 59 406 60 1466 61 435 62 1425 63 431 64 1695 65 464 66 1658 67 528 68 1934 69 572 70 1764 71 595 72 2219 73 630 74 2061 75 650 76 2450 77 656 78 2378 79 741 80 2691 81 780 82 2550 83 820 84 3084 85 826 86 2814 87 938 88 3332 89 946 90 3151 91 936 92 3665 93 1080 94 3381 95 1046 96 4186 97 1128 98 3627 99 1168 100 4322 101 1225 102 4208 103 1275 104 4753 105 1300 106 4329 107 1378 108 5312 109 1431 110 4602 111 1566 112 5497 113 1540 114 5318 115 1564 116 5945 117 1673 118 5394 119 1646 120 6722 121 1730 122 5775 123 1940 124 6827 125 1862 126 6415 127 1953 128 7359 129 2142 130 6528 131 2080 132 8150 133 2076 134 6996 135 2244 136 8354 137 2278 138 7928 139 2346 140 8680 141 2576 142 7875 143 2390 144 9871 145 2536 146 8334 147 2736 148 9839 149 2701 150 9414 151 2775 152 10534 153 2956 154 9132 155 2912 156 11598 157 3003 158 9789 159 3302 160 11731 161 3086 162 10960 163 3240 164 12152 165 3448 166 10824 167 3403 168 13700 169 3429 170 11394 171 3734 172 13400 173 3655 174 12818 175 3667 176 14172 177 4118 178 12474 179 3916 180 15613 181 4005 182 12888 183 4410 184 15653 185 4196 186 14708 187 4156 188 16079 189 4528 190 14334 191 4465 192 18234 193 4560 194 14856 195 4912 196 17418 197 4753 198 16492 199 4851 200 18720 201 5346 202 16125 203 4976 204 20324 205 5182 206 16779 207 5563 208 20041 209 5222 210 18892 211 5460 212 20555 213 6020 214 18126 215 5714 216 23208 217 5706 218 18819 219 6372 220 22238 221 5846 222 21158 223 6105 224 23369 225 6593 226 20244 227 6328 228 25602 229 6441 230 21228 231 6892 232 25229 233 6670 234 23305 235 6856 236 25580 237 7488 238 22350 239 7021 240 29234 241 7140 242 23100 243 7756 244 27377 245 7401 246 26108 247 7338 248 28927 249 8282 250 25182 251 7750 252 31277 253 7720 254 25641 255 8620 256 30847 257 8128 258 28778 259 8196 260 31396 261 8989 262 27300 263 8515 264 35246 265 8764 266 28056 267 9548 268 33134 269 8911 270 31764 271 9045 272 34842 273 9756 274 29886 275 9288 276 37988 277 9453 278 30774 279 10313 280 37552 281 9730 282 34508 283 9870 284 37277 285 10864 286 32238 287 10106 288 42215 289 10196 290 34104 291 11376 292 39440 293 10585 294 37524 295 10906 296 41539 297 11556 298 35409 299 10832 300 45572 301 11136 302 36375 303 12350 304 43774 305 11672 306 40480 307 11628 308 43768 309 12852 310 39072 311 11935 312 49814 313 12090 314 39351 315 13208 316 46295 317 12403 318 44078 319 12382 320 49459 321 13886 322 41418 323 12656 324 52653 325 13075 326 42444 327 14418 328 51212 329 13346 330 48016 331 13530 332 51170 333 14831 334 44571 335 14126 336 58260 337 14028 338 45441 339 15512 340 54470 341 14180 342 50842 343 14526 344 56428 345 16132 346 47859 347 14878 348 61142 349 15051 350 50115 351 16300 352 58924 353 15400 354 54818 355 15892 356 58940 357 16984 358 51264 359 15931 360 67849 361 15984 362 52425 363 17630 364 61564 365 16814 366 58658 367 16653 368 64701 369 18298 370 56004 371 17036 372 70080 373 17205 374 55572 375 19156 376 67619 377 17348 378 62568 379 17766 380 68386 381 19656 382 58425 383 18145 384 76666 385 18572 386 59664 387 20168 388 70154 389 18721 390 67648 391 18646 392 73824 393 20930 394 62181 395 19736 396 79258 397 19503 398 63459 399 21348 400 78164 401 19900 402 70958 403 19860 404 76127 405 22325 406 66336 407 20306 408 86540 409 20706 410 68982 411 22916 412 79205 413 21176 414 75115 415 21814 416 82841 417 23598 418 69618 419 21736 420 91396 421 21945 422 71400 423 24181 424 86303 425 22602 426 79808 427 22656 428 85544 429 24544 430 75978 431 23005 432 97496 433 23220 434 75942 435 25984 436 88805 437 23348 438 84428 439 23871 440 94694 441 26265 442 77838 443 24310 444 100554 445 25126 446 79809 447 27158 448 97065 449 24976 450 90795 451 25000 452 95510 453 27900 454 82716 455 26140 456 108698 457 25878 458 84189 459 28248 460 100976 461 26335 462 94156 463 26565 464 103749 465 29788 466 87174 467 27028 468 111575 469 27396 470 90984 471 30186 472 107264 473 27530 474 99068 475 28342 476 106306 477 30883 478 91749 479 28441 480 123218 481 28416 482 93300 483 31576 484 109403 485 29906 486 104120 487 29403 488 114757 489 32562 490 99657 491 29890 492 123920 493 29806 494 97458 495 33578 496 118807 497 30806 498 109478 499 30876 500 119650 501 34196 502 101250 503 31375 504 134089 505 32452 506 102468 507 34758 508 120899 509 32131 510 117052 511 32586 512 126719 513 35452 514 106176 515 33764 516 136518 517 32956 518 108660 519 36722 520 133132 521 33670 522 120397 523 33930 524 128702 525 38032 526 111219 527 34106 528 146942 529 34529 530 116028 531 38404 532 133252 533 34970 534 126068 535 36466 536 138754 537 39338 538 116379 539 36102 540 152604 541 36315 542 118125 543 40230 544 142954 545 37856 546 132244 547 37128 548 140864 549 41093 550 124668 551 37298 552 160604 553 38226 554 123441 555 42760 556 145040 557 38503 558 137857 559 38502 560 156576 561 42412 562 127050 563 39340 564 163544 565 40714 566 128874 567 43779 568 156017 569 40186 570 146824 571 40470 572 153010 573 44840 574 133722 575 41775 576 175927 577 41328 578 134052 579 45792 580 161756 581 42236 582 150008 583 42010 584 165028 585 47312 586 138189 587 42778 588 178866 589 42672 590 144114 591 47726 592 170107 593 43660 594 156156 595 45176 596 166835 597 48708 598 143328 599 44551 600 194208 601 44850 602 147228 603 49706 604 171377 605 46563 606 162758 607 45753 608 179150 609 50668 610 154152 611 46076 612 192862 613 46665 614 151776 615 52708 616 185008 617 47278 618 169328 619 47586 620 185188 621 52320 622 155775 623 48626 624 206598 625 49690 626 157794 627 53176 628 185369 629 48746 630 181832 631 49455 632 193579 633 54810 634 161871 635 51536 636 208658 637 50571 638 163638 639 55903 640 204147 641 51040 642 182858 643 51360 644 196294 645 58072 646 167256 647 52003 648 222991 649 52162 650 174639 651 58032 652 199910 653 52975 654 189818 655 54862 656 209412 657 59138 658 176190 659 53956 660 229672 661 54285 662 176550 663 59476 664 213878 665 56644 666 197335 667 54808 668 209909 669 61272 670 186294 671 55790 672 242036 673 56280 674 183036 675 63296 676 214644 677 56953 678 204128 679 57846 680 229742 681 63506 682 187200 683 57970 684 241832 685 60046 686 191646 687 64638 688 230596 689 58712 690 216508 691 59340 692 225365 693 65852 694 194106 695 61826 696 257438 697 59956 698 196359 699 66932 700 238561 701 61075 702 218940 703 60966 704 241420 705 69580 706 200904 707 62756 708 259262 709 62481 710 209412 711 69389 712 246224 713 62690 714 227920 715 65048 716 241370 717 70448 718 207819 719 64261 720 283729 721 65286 722 209682 723 71640 724 246827 725 66807 726 234162 727 65703 728 259460 729 72728 730 221478 731 65996 732 277350 733 66795 734 217221 735 75930 736 263821 737 67406 738 242902 739 67896 740 265000 741 74520 742 224508 743 68635 744 294776 745 71116 746 224409 747 76678 748 263048 749 70496 750 256420 751 70125 752 276027 753 77750 754 228708 755 73052 756 298624 757 71253 758 231714 759 78364 760 287914 761 72010 762 258308 763 73176 764 275027 765 81878 766 236649 767 72878 768 315642 769 73536 770 249348 771 81536 772 280850 773 74305 774 267460 775 76453 776 292894 777 83124 778 244149 779 74972 780 322600 781 75760 782 245718 783 83772 784 303108 785 79016 786 274958 787 77028 788 292679 789 85412 790 259704 791 78686 792 335638 793 77940 794 254331 795 88792 796 298685 797 79003 798 285508 799 78946 800 320844 801 88294 802 259500 803 80120 804 335274 805 83480 806 261588 807 89378 808 317747 809 81406 810 300785 811 81810 812 313732 813 90720 814 267402 815 85214 816 356540 817 82518 818 269994 819 92500 820 326138 821 83845 822 300908 823 84255 824 330553 825 95070 826 278676 827 85078 828 356425 829 85491 830 286878 831 94806 832 338169 833 86862 834 309818 835 89476 836 329230 837 95896 838 283404 839 87571 840 389044 841 87689 842 286125 843 97580 844 336002 845 91389 846 320125 847 90259 848 351831 849 98982 850 299970 851 89516 852 376940 853 90525 854 298032 855 102710 856 356924 857 91378 858 327736 859 91806 860 359086 861 102352 862 299925 863 92665 864 401784 865 96064 866 302724 867 102776 868 358978 869 93932 870 346384 871 94146 872 370489 873 105056 874 307248 875 98848 876 398688 877 95703 878 311199 879 106142 880 390102 881 96580 882 351645 883 97020 884 367954 885 110344 886 316914 887 97903 888 421970 889 99546 890 330174 891 108830 892 375515 893 98696 894 356318 895 102886 896 397161 897 109708 898 325584 899 99932 900 432872 901 100546 902 328800 903 112716 904 398378 905 105212 906 366008 907 102378 908 389174 909 113983 910 349212 911 103285 912 446826 913 103750 914 337326 915 118048 916 396095 917 105956 918 376488 919 105111 920 423992 921 116586 922 343275 923 105800 924 447988 925 109297 926 346269 927 118583 928 421525 929 107416 930 396436 931 108684 932 410120 933 119660 934 352296 935 111892 936 470947 937 109278 938 360000 939 121212 940 429740 941 110215 942 395858 943 110050 944 436824 945 126648 946 361878 947 111628 948 467592 949 111882 950 375330 951 124346 952 446314 953 113050 954 407995 955 117232 956 431615 957 125296 958 370689 959 115946 960 508946 961 114615 962 373488 963 128056 964 438902 965 119714 966 420184 967 116403 968 457713 969 128068 970 392634 971 117370 972 493222 973 119376 974 383211 975 133354 976 467197 977 118828 978 426878 979 119392 980 472407 981 132929 982 389550 983 120295 984 519416 985 124756 986 391686 987 134944 988 460342 989 121112 990 452642 991 122265 992 482279 993 135630 994 404562 995 127316 996 516578 997 123753 998 402384 999 137188 1000 501898