0 5 1 4 2 6 3 11 4 16 5 24 6 26 7 14 8 15 9 20 10 28 11 16 12 16 13 24 14 16 15 24 16 38 17 64 18 62 19 75 20 72 21 60 22 68 23 62 24 106 25 90 26 106 27 90 28 82 29 106 30 93 31 114 32 120 33 94 34 136 35 152 36 174 37 202 38 221 39 252 40 216 41 232 42 246 43 270 44 320 45 312 46 358 47 372 48 360 49 384 50 364 51 486 52 414 53 460 54 592 55 568 56 618 57 640 58 712 59 645 60 702 61 738 62 914 63 830 64 726 65 974 66 994 67 850 68 975 69 1096 70 1030 71 1098 72 1116 73 1204 74 1212 75 1162 76 1295 77 1262 78 1444 79 1347 80 1404 81 1558 82 1555 83 1610 84 1688 85 1782 86 1555 87 1810 88 1940 89 1960 90 1910 91 2122 92 1888 93 1857 94 2310 95 2174 96 2050 97 2312 98 2424 99 2326 100 2603 101 2526 102 2702 103 2766 104 2538 105 2902 106 2814 107 3044 108 3234 109 3128 110 3182 111 3358 112 3450 113 3362 114 3412 115 3504 116 3586 117 3488 118 3540 119 3820 120 3856 121 3763 122 4078 123 4098 124 4342 125 4265 126 4344 127 4604 128 4606 129 4658 130 4938 131 4738 132 4852 133 4918 134 5179 135 5282 136 5034 137 5398 138 5618 139 5522 140 5758 141 5918 142 5820 143 6016 144 5952 145 6030 146 6140 147 6542 148 6138 149 6712 150 6604 151 6800 152 6932 153 6864 154 6774 155 7180 156 7200 157 7358 158 7616 159 7766 160 7632 161 7816 162 7868 163 7931 164 8232 165 8138 166 8826 167 8718 168 8864 169 8948 170 9067 171 9474 172 9488 173 8948 174 9164 175 9552 176 9572 177 9654 178 10018 179 9582 180 10444 181 10132 182 10656 183 10391 184 10462 185 10530 186 10602 187 11148 188 11228 189 11522 190 11614 191 11426 192 12054 193 12168 194 11969 195 12318 196 11956 197 12068 198 12454 199 12547 200 12578 201 13046 202 13308 203 13330 204 13412 205 13762 206 13865 207 13838 208 13982 209 14474 210 14118 211 14620 212 14528 213 14496 214 14626 215 15073 216 15188 217 15476 218 15715 219 15626 220 15872 221 16652 222 16416 223 16748 224 16618 225 16530 226 16660 227 17448 228 17368 229 17846 230 17607 231 17452 232 18192 233 18546 234 18196 235 18528 236 18660 237 18618 238 19798 239 19094 240 19742 241 19681 242 19512 243 19698 244 20494 245 20093 246 20012 247 20104 248 20050 249 20562 250 21250 251 21169 252 21426 253 21504 254 21866 255 22252 256 22182 257 22220 258 21924 259 22980 260 22424 261 22668 262 23138 263 23444 264 23322 265 23418 266 23486 267 23819 268 24140 269 24542 270 24252 271 25481 272 24840 273 25077 274 25796 275 25886 276 26244 277 25590 278 26622 279 26214 280 27116 281 27110 282 27258 283 27338 284 27523 285 28090 286 28316 287 28328 288 29324 289 28942 290 28208 291 29166 292 29466 293 29978 294 30110 295 30630 296 30487 297 29978 298 30586 299 30924 300 31270 301 31655 302 32288 303 32344 304 32099 305 32444 306 33672 307 33682 308 33576 309 32878 310 34026 311 34178 312 34432 313 34398 314 34688 315 35368 316 35644 317 35444 318 35858 319 36350 320 36869 321 36716 322 37196 323 37350 324 36946 325 36662 326 36770 327 37366 328 38218 329 38980 330 39106 331 38562 332 38433 333 39756 334 39786 335 40260 336 39106 337 40494 338 39746 339 40578 340 40621 341 41130 342 40812 343 41556 344 41089 345 43646 346 42208 347 42600 348 43030 349 44188 350 43205 351 43974 352 44478 353 44940 354 45493 355 46304 356 45550 357 45834 358 45576 359 46086 360 46088 361 46396 362 46764 363 46755 364 48506 365 47140 366 48536 367 47364 368 48456 369 47754 370 50088 371 49562 372 50003 373 50714 374 49938 375 50149 376 49618 377 50918 378 50386 379 50828 380 51722 381 51816 382 52604 383 53018 384 52334 385 51926 386 53288 387 52882 388 54138 389 54378 390 54712 391 54762 392 54292 393 55850 394 55878 395 55454 396 56052 397 56593 398 57330 399 57076 400 57630 401 57886 402 58034 403 58300 404 58522 405 59195 406 60084 407 59910 408 60404 409 60932 410 59828 411 61569 412 60390 413 61602 414 62035 415 62176 416 63030 417 63287 418 63540 419 64056 420 64032 421 64543 422 65148 423 65684 424 65699 425 65962 426 66474 427 66173 428 66340 429 68054 430 67771 431 68300 432 67646 433 67840 434 68140 435 68874 436 69445 437 71240 438 70438 439 70530 440 71086 441 70602 442 71102 443 72300 444 71167 445 73040 446 73724 447 73584 448 74946 449 74404 450 74364 451 75361 452 75320 453 75954 454 76212 455 76700 456 78400 457 77268 458 76898 459 78360 460 78528 461 80070 462 78520 463 79215 464 79962 465 80862 466 79828 467 80574 468 81084 469 82002 470 82072 471 82615 472 82780 473 82486 474 83082 475 84169 476 85028 477 84386 478 85430 479 83879 480 84514 481 85602 482 87104 483 86915 484 87238 485 86696 486 88398 487 87618 488 88998 489 88872 490 90668 491 89985 492 89752 493 90634 494 90694 495 91187 496 92704 497 92468 498 92636 499 92868 500 93628 501 94070 502 94908 503 95449 504 96516 505 95854 506 96984 507 96740 508 97950 509 96978 510 99129 511 98596 512 97802 513 98990 514 99304 515 99850 516 99510 517 100244 518 101870 519 100958 520 101420 521 102364 522 102084 523 102288 524 102916 525 103049 526 103864 527 103854 528 104168 529 104818 530 105966 531 106553 532 105672 533 106202 534 107582 535 108276 536 107870 537 108110 538 109200 539 109196 540 110540 541 109848 542 111086 543 110722 544 111450 545 112079 546 113532 547 112950 548 113982 549 113212 550 114022 551 113010 552 113698 553 114851 554 116722 555 116774 556 116944 557 117493 558 118296 559 118160 560 118857 561 118366 562 118080 563 118272 564 119194 565 121424 566 120686 567 121586 568 122608 569 122742 570 122824 571 122628 572 123344 573 122771 574 124862 575 125816 576 125420 577 126683 578 126166 579 128280 580 126091 581 125940 582 127654 583 127834 584 129068 585 129257 586 130136 587 129416 588 131420 589 132578 590 130906 591 132947 592 133384 593 134090 594 132608 595 133691 596 133376 597 135220 598 134359 599 137192 600 136736 601 137168 602 138517 603 136530 604 139536 605 138000 606 139458 607 139768 608 141070 609 140340 610 142051 611 141908 612 142600 613 142848 614 142551 615 142572 616 143656 617 144615 618 145322 619 146274 620 146578 621 145747 622 146612 623 147038 624 147636 625 149301 626 148840 627 148514 628 150062 629 150766 630 152876 631 151345 632 153408 633 154386 634 153144 635 153084 636 155373 637 153014 638 154808 639 155040 640 156878 641 156670 642 158908 643 158692 644 158250 645 157334 646 160527 647 160368 648 161344 649 160715 650 161166 651 160872 652 163216 653 165190 654 163058 655 163514 656 162918 657 163148 658 166858 659 166468 660 164424 661 168554 662 168556 663 168577 664 169404 665 170754 666 170446 667 173094 668 172356 669 171014 670 172140 671 171808 672 172564 673 173312 674 174132 675 174724 676 175034 677 176984 678 175612 679 176936 680 178568 681 178762 682 180921 683 178782 684 179462 685 181682 686 182171 687 182166 688 181794 689 182624 690 183399 691 184584 692 185636 693 185894 694 187502 695 186841 696 187000 697 188756 698 188558 699 188914 700 189085 701 190970 702 191014 703 190866 704 191864 705 192014 706 191628 707 191075 708 194776 709 193842 710 194678 711 193543 712 195266 713 195664 714 198562 715 197346 716 199690 717 196854 718 199010 719 200562 720 200344 721 201490 722 201788 723 202298 724 202766 725 201958 726 204742 727 204142 728 206694 729 206600 730 207974 731 208166 732 209386 733 208124 734 209899 735 210458 736 211044 737 211622 738 211042 739 212452 740 213170 741 213122 742 213098 743 214303 744 214748 745 215020 746 215564 747 217656 748 216098 749 216597 750 218240 751 218088 752 219048 753 220356 754 220370 755 222701 756 221924 757 224346 758 223604 759 225795 760 224208 761 224254 762 224011 763 227162 764 226964 765 227487 766 227468 767 229072 768 228666 769 229290 770 230594 771 232718 772 232376 773 230480 774 233696 775 231025 776 234066 777 234728 778 235048 779 235986 780 237184 781 237295 782 237628 783 239100 784 239364 785 240414 786 241464 787 241999 788 242440 789 242862 790 244762 791 244620 792 243929 793 243764 794 243724 795 245658 796 245178 797 248148 798 248872 799 246308 800 249898 801 249545 802 247744 803 248128 804 250306 805 252588 806 251086 807 253175 808 256258 809 253866 810 257581 811 255592 812 257916 813 256618 814 257834 815 259890 816 260066 817 258803 818 260546 819 259756 820 261338 821 262210 822 263398 823 262736 824 263303 825 265972 826 266468 827 268124 828 265296 829 268644 830 266834 831 268738 832 269474 833 272208 834 271990 835 273170 836 272274 837 274092 838 276782 839 274600 840 276352 841 277220 842 277086 843 278818 844 278012 845 277624 846 279906 847 279992 848 278152 849 282058 850 283194 851 283958 852 283216 853 285456 854 285220 855 285886 856 286558 857 287248 858 289700 859 287436 860 291104 861 290220 862 292446 863 291678 864 292158 865 295706 866 295100 867 296567 868 298360 869 296576 870 297270 871 298076 872 298466 873 300330 874 299240 875 299980 876 300159 877 300584 878 302292 879 303076 880 304290 881 301546 882 308346 883 306908 884 307250 885 306440 886 307611 887 309152 888 310806 889 309490 890 310176 891 309990 892 313096 893 313958 894 314840 895 315153 896 315338 897 317490 898 319816 899 318068 900 317312 901 318941 902 318974 903 320305 904 324668 905 320928 906 322890 907 322493 908 323786 909 324258 910 326454 911 328802 912 328364 913 328748 914 331700 915 329840 916 331170 917 330656 918 331192 919 335084 920 335134 921 334798 922 333316 923 334166 924 333074 925 335340 926 337450 927 337602 928 337722 929 338758 930 339522 931 340226 932 341178 933 342808 934 341673 935 343424 936 345168 937 344633 938 346612 939 346296 940 347781 941 347226 942 351594 943 349464 944 350544 945 350876 946 352752 947 352649 948 355008 949 355234 950 356614 951 356130 952 357180 953 358920 954 359518 955 361342 956 363229 957 365516 958 365584 959 360844 960 364732 961 366856 962 366746 963 365858 964 367850 965 368252 966 368889 967 369806 968 372746 969 372284 970 370922 971 371420 972 373924 973 373622 974 374130 975 375954 976 377998 977 377504 978 378736 979 378040 980 379042 981 379596 982 382868 983 381874 984 384440 985 381990 986 385650 987 385823 988 384772 989 388086 990 391118 991 389794 992 389236 993 387848 994 389756 995 392594 996 393230 997 391310 998 393926 999 395184 1000 396902