1 0 2 0 3 2 4 2 5 6 6 8 7 12 8 16 9 26 10 30 11 38 12 44 13 56 14 60 15 74 16 82 17 96 18 108 19 128 20 138 21 154 22 166 23 188 24 196 25 220 26 238 27 262 28 278 29 304 30 324 31 344 32 366 33 398 34 416 35 452 36 468 37 506 38 526 39 562 40 588 41 616 42 644 43 686 44 714 45 754 46 780 47 824 48 848 49 894 50 930 51 976 52 1008 53 1056 54 1090 55 1134 56 1170 57 1224 58 1256 59 1308 60 1350 61 1406 62 1438 63 1500 64 1540 65 1592 66 1638 67 1694 68 1744 69 1804 70 1856 71 1914 72 1954 73 2026 74 2072 75 2136 76 2180 77 2258 78 2310 79 2374 80 2432 81 2504 82 2548 83 2626 84 2678 85 2756 86 2808 87 2892 88 2950 89 3022 90 3090 91 3164 92 3220 93 3300 94 3366 95 3450 96 3510 97 3600 98 3664 99 3754 100 3822 101 3910 102 3984 103 4068 104 4144 105 4238 106 4298 107 4394 108 4464 109 4560 110 4628 111 4734 112 4810 113 4902 114 4980 115 5088 116 5162 117 5254 118 5338 119 5448 120 5524 121 5636 122 5718 123 5818 124 5906 125 6016 126 6100 127 6196 128 6298 129 6414 130 6506 131 6612 132 6704 133 6822 134 6902 135 7030 136 7116 137 7236 138 7336 139 7458 140 7546 141 7670 142 7764 143 7884 144 7976 145 8122 146 8218 147 8342 148 8448 149 8576 150 8682 151 8802 152 8910 153 9044 154 9148 155 9292 156 9398 157 9526 158 9630 159 9772 160 9880 161 10016 162 10134 163 10282 164 10386 165 10536 166 10648 167 10790 168 10898 169 11046 170 11180 171 11320 172 11436 173 11590 174 11710 175 11858 176 11980 177 12124 178 12244 179 12414 180 12542 181 12690 182 12816 183 12976 184 13098 185 13258 186 13386 187 13552 188 13676 189 13840 190 13982 191 14134 192 14266 193 14432 194 14568 195 14736 196 14878 197 15066 198 15180 199 15360 200 15508 201 15678 202 15806 203 15974 204 16136 205 16304 206 16452 207 16638 208 16766 209 16946 210 17100 211 17276 212 17420 213 17602 214 17762 215 17940 216 18096 217 18284 218 18430 219 18618 220 18770 221 18976 222 19112 223 19308 224 19466 225 19658 226 19818 227 20008 228 20168 229 20364 230 20542 231 20734 232 20900 233 21096 234 21256 235 21458 236 21618 237 21818 238 21996 239 22184 240 22372 241 22570 242 22742 243 22954 244 23112 245 23336 246 23496 247 23730 248 23902 249 24108 250 24288 251 24496 252 24678 253 24882 254 25054 255 25296 256 25460 257 25688 258 25870 259 26094 260 26278 261 26492 262 26680 263 26896 264 27082 265 27318 266 27512 267 27732 268 27932 269 28158 270 28334 271 28570 272 28772 273 29008 274 29196 275 29430 276 29626 277 29850 278 30056 279 30292 280 30484 281 30738 282 30934 283 31180 284 31368 285 31616 286 31818 287 32046 288 32262 289 32512 290 32732 291 32976 292 33186 293 33434 294 33634 295 33884 296 34092 297 34354 298 34566 299 34830 300 35040 301 35284 302 35504 303 35766 304 35962 305 36222 306 36452 307 36716 308 36920 309 37194 310 37422 311 37666 312 37900 313 38160 314 38386 315 38662 316 38890 317 39164 318 39372 319 39648 320 39870 321 40134 322 40366 323 40656 324 40892 325 41156 326 41402 327 41678 328 41902 329 42180 330 42420 331 42702 332 42930 333 43226 334 43468 335 43732 336 43980 337 44262 338 44498 339 44798 340 45052 341 45340 342 45572 343 45882 344 46110 345 46390 346 46644 347 46944 348 47198 349 47490 350 47754 351 48032 352 48284 353 48588 354 48838 355 49130 356 49382 357 49704 358 49952 359 50260 360 50522 361 50830 362 51074 363 51392 364 51644 365 51966 366 52226 367 52538 368 52808 369 53108 370 53380 371 53678 372 53946 373 54262 374 54548 375 54856 376 55128 377 55446 378 55718 379 56034 380 56304 381 56616 382 56894 383 57230 384 57506 385 57824 386 58096 387 58432 388 58718 389 59038 390 59326 391 59656 392 59932 393 60272 394 60558 395 60898 396 61164 397 61504 398 61792 399 62142 400 62414 401 62754 402 63052 403 63376 404 63672 405 64018 406 64290 407 64646 408 64952 409 65300 410 65596 411 65922 412 66238 413 66572 414 66868 415 67216 416 67522 417 67878 418 68178 419 68548 420 68832 421 69184 422 69482 423 69842 424 70158 425 70516 426 70820 427 71176 428 71490 429 71862 430 72164 431 72508 432 72820 433 73202 434 73510 435 73886 436 74200 437 74544 438 74876 439 75258 440 75566 441 75934 442 76268 443 76644 444 76952 445 77334 446 77658 447 78020 448 78344 449 78708 450 79066 451 79430 452 79758 453 80148 454 80464 455 80852 456 81170 457 81566 458 81898 459 82288 460 82644 461 83008 462 83338 463 83734 464 84060 465 84456 466 84784 467 85198 468 85518 469 85926 470 86272 471 86652 472 86988 473 87386 474 87726 475 88130 476 88488 477 88888 478 89208 479 89634 480 89978 481 90376 482 90708 483 91136 484 91486 485 91882 486 92258 487 92648 488 93016 489 93424 490 93790 491 94190 492 94534 493 94976 494 95340 495 95730 496 96106 497 96510 498 96868 499 97276 500 97660 501 98078 502 98422 503 98862 504 99220 505 99652 506 100008 507 100434 508 100802 509 101230 510 101624 511 102040 512 102418 513 102842 514 103218 515 103652 516 104008 517 104456 518 104838 519 105266 520 105658 521 106092 522 106464 523 106888 524 107278 525 107730 526 108098 527 108552 528 108924 529 109382 530 109758 531 110202 532 110592 533 111012 534 111428 535 111874 536 112254 537 112722 538 113112 539 113568 540 113948 541 114410 542 114786 543 115246 544 115652 545 116112 546 116514 547 116950 548 117366 549 117816 550 118212 551 118680 552 119086 553 119538 554 119950 555 120424 556 120824 557 121280 558 121690 559 122142 560 122566 561 123048 562 123456 563 123926 564 124322 565 124814 566 125208 567 125676 568 126092 569 126582 570 127002 571 127474 572 127900 573 128356 574 128780 575 129258 576 129682 577 130168 578 130592 579 131092 580 131514 581 131986 582 132430 583 132900 584 133304 585 133820 586 134254 587 134750 588 135166 589 135672 590 136092 591 136580 592 137010 593 137498 594 137948 595 138432 596 138896 597 139378 598 139810 599 140306 600 140748 601 141228 602 141680 603 142206 604 142622 605 143142 606 143600 607 144108 608 144528 609 145026 610 145490 611 146020 612 146456 613 146980 614 147398 615 147906 616 148366 617 148884 618 149312 619 149856 620 150326 621 150842 622 151282 623 151812 624 152264 625 152764 626 153230 627 153774 628 154212 629 154744 630 155224 631 155742 632 156206 633 156718 634 157192 635 157688 636 158188 637 158734 638 159194 639 159710 640 160188 641 160728 642 161176 643 161722 644 162182 645 162740 646 163212 647 163752 648 164226 649 164758 650 165250 651 165784 652 166252 653 166820 654 167286 655 167846 656 168326 657 168872 658 169360 659 169868 660 170378 661 170938 662 171416 663 171976 664 172440 665 173010 666 173474 667 174046 668 174548 669 175080 670 175588 671 176158 672 176642 673 177194 674 177688 675 178256 676 178726 677 179314 678 179822 679 180384 680 180892 681 181456 682 181962 683 182506 684 183022 685 183600 686 184076 687 184664 688 185186 689 185758 690 186242 691 186840 692 187348 693 187898 694 188418 695 188986 696 189516 697 190076 698 190604 699 191194 700 191682 701 192286 702 192788 703 193368 704 193896 705 194490 706 195010 707 195582 708 196120 709 196708 710 197214 711 197806 712 198350 713 198932 714 199448 715 200052 716 200590 717 201150 718 201702 719 202300 720 202816 721 203424 722 203966 723 204574 724 205082 725 205708 726 206228 727 206842 728 207350 729 207978 730 208528 731 209116 732 209668 733 210274 734 210814 735 211426 736 211956 737 212572 738 213116 739 213746 740 214302 741 214890 742 215448 743 216064 744 216598 745 217194 746 217766 747 218404 748 218936 749 219576 750 220142 751 220746 752 221294 753 221924 754 222480 755 223104 756 223662 757 224294 758 224838 759 225476 760 226040 761 226662 762 227202 763 227870 764 228420 765 229064 766 229628 767 230262 768 230826 769 231442 770 232036 771 232648 772 233240 773 233890 774 234466 775 235104 776 235668 777 236328 778 236890 779 237522 780 238130 781 238760 782 239332 783 240000 784 240570 785 241230 786 241778 787 242448 788 243024 789 243684 790 244286 791 244930 792 245500 793 246148 794 246756 795 247394 796 247970 797 248650 798 249256 799 249896 800 250512 801 251186 802 251754 803 252406 804 253028 805 253688 806 254276 807 254950 808 255558 809 256224 810 256812 811 257496 812 258074 813 258734 814 259374 815 260064 816 260632 817 261308 818 261930 819 262614 820 263202 821 263888 822 264480 823 265164 824 265782 825 266494 826 267072 827 267760 828 268364 829 269058 830 269658 831 270362 832 270996 833 271656 834 272284 835 272998 836 273582 837 274274 838 274876 839 275600 840 276216 841 276926 842 277542 843 278224 844 278860 845 279564 846 280194 847 280870 848 281518 849 282248 850 282876 851 283564 852 284190 853 284882 854 285518 855 286220 856 286868 857 287548 858 288218 859 288918 860 289556 861 290264 862 290880 863 291606 864 292218 865 292974 866 293620 867 294324 868 294964 869 295706 870 296358 871 297058 872 297692 873 298440 874 299054 875 299798 876 300446 877 301168 878 301812 879 302540 880 303214 881 303894 882 304586 883 305332 884 305984 885 306708 886 307350 887 308106 888 308714 889 309468 890 310156 891 310882 892 311530 893 312262 894 312944 895 313672 896 314340 897 315090 898 315706 899 316510 900 317160 901 317924 902 318580 903 319314 904 320002 905 320718 906 321408 907 322168 908 322822 909 323586 910 324274 911 325012 912 325664 913 326420 914 327122 915 327854 916 328566 917 329312 918 330000 919 330748 920 331442 921 332214 922 332858 923 333616 924 334320 925 335102 926 335758 927 336566 928 337232 929 337988 930 338688 931 339458 932 340146 933 340910 934 341624 935 342404 936 343068 937 343850 938 344538 939 345286 940 346016 941 346796 942 347506 943 348266 944 348986 945 349784 946 350448 947 351244 948 351926 949 352722 950 353442 951 354232 952 354944 953 355696 954 356418 955 357202 956 357886 957 358684 958 359416 959 360194 960 360914 961 361718 962 362444 963 363204 964 363936 965 364746 966 365458 967 366246 968 366984 969 367788 970 368488 971 369310 972 370018 973 370812 974 371508 975 372368 976 373094 977 373890 978 374634 979 375412 980 376140 981 376952 982 377670 983 378498 984 379206 985 380052 986 380772 987 381572 988 382318 989 383118 990 383848 991 384656 992 385436 993 386246 994 386962 995 387802 996 388544 997 389344 998 390100 999 390914 1000 391674