0 1 1 1 2 2 3 4 4 5 5 6 6 8 7 9 8 10 9 11 10 13 11 14 12 15 13 16 14 18 15 19 16 20 17 21 18 23 19 24 20 25 21 26 22 28 23 29 24 30 25 31 26 32 27 34 28 35 29 36 30 37 31 38 32 40 33 41 34 42 35 43 36 44 37 46 38 47 39 48 40 49 41 50 42 52 43 53 44 54 45 55 46 56 47 58 48 59 49 60 50 61 51 62 52 64 53 65 54 66 55 67 56 68 57 70 58 71 59 72 60 73 61 74 62 75 63 77 64 78 65 79 66 80 67 81 68 83 69 84 70 85 71 86 72 87 73 88 74 90 75 91 76 92 77 93 78 94 79 95 80 97 81 98 82 99 83 100 84 101 85 103 86 104 87 105 88 106 89 107 90 108 91 110 92 111 93 112 94 113 95 114 96 115 97 117 98 118 99 119 100 120 101 121 102 122 103 124 104 125 105 126 106 127 107 128 108 129 109 131 110 132 111 133 112 134 113 135 114 136 115 138 116 139 117 140 118 141 119 142 120 143 121 145 122 146 123 147 124 148 125 149 126 150 127 152 128 153 129 154 130 155 131 156 132 157 133 159 134 160 135 161 136 162 137 163 138 164 139 165 140 167 141 168 142 169 143 170 144 171 145 172 146 174 147 175 148 176 149 177 150 178 151 179 152 181 153 182 154 183 155 184 156 185 157 186 158 187 159 189 160 190 161 191 162 192 163 193 164 194 165 196 166 197 167 198 168 199 169 200 170 201 171 203 172 204 173 205 174 206 175 207 176 208 177 209 178 211 179 212 180 213 181 214 182 215 183 216 184 218 185 219 186 220 187 221 188 222 189 223 190 224 191 226 192 227 193 228 194 229 195 230 196 231 197 233 198 234 199 235 200 236 201 237 202 238 203 239 204 241 205 242 206 243 207 244 208 245 209 246 210 247 211 249 212 250 213 251 214 252 215 253 216 254 217 256 218 257 219 258 220 259 221 260 222 261 223 262 224 264 225 265 226 266 227 267 228 268 229 269 230 270 231 272 232 273 233 274 234 275 235 276 236 277 237 279 238 280 239 281 240 282 241 283 242 284 243 285 244 287 245 288 246 289 247 290 248 291 249 292 250 293 251 295 252 296 253 297 254 298 255 299 256 300 257 301 258 303 259 304 260 305 261 306 262 307 263 308 264 309 265 311 266 312 267 313 268 314 269 315 270 316 271 318 272 319 273 320 274 321 275 322 276 323 277 324 278 326 279 327 280 328 281 329 282 330 283 331 284 332 285 334 286 335 287 336 288 337 289 338 290 339 291 340 292 342 293 343 294 344 295 345 296 346 297 347 298 348 299 350 300 351 301 352 302 353 303 354 304 355 305 356 306 358 307 359 308 360 309 361 310 362 311 363 312 364 313 366 314 367 315 368 316 369 317 370 318 371 319 372 320 374 321 375 322 376 323 377 324 378 325 379 326 380 327 382 328 383 329 384 330 385 331 386 332 387 333 388 334 390 335 391 336 392 337 393 338 394 339 395 340 396 341 398 342 399 343 400 344 401 345 402 346 403 347 404 348 406 349 407 350 408 351 409 352 410 353 411 354 412 355 413 356 415 357 416 358 417 359 418 360 419 361 420 362 421 363 423 364 424 365 425 366 426 367 427 368 428 369 429 370 431 371 432 372 433 373 434 374 435 375 436 376 437 377 439 378 440 379 441 380 442 381 443 382 444 383 445 384 447 385 448 386 449 387 450 388 451 389 452 390 453 391 455 392 456 393 457 394 458 395 459 396 460 397 461 398 462 399 464 400 465 401 466 402 467 403 468 404 469 405 470 406 472 407 473 408 474 409 475 410 476 411 477 412 478 413 480 414 481 415 482 416 483 417 484 418 485 419 486 420 488 421 489 422 490 423 491 424 492 425 493 426 494 427 495 428 497 429 498 430 499 431 500 432 501 433 502 434 503 435 505 436 506 437 507 438 508 439 509 440 510 441 511 442 513 443 514 444 515 445 516 446 517 447 518 448 519 449 520 450 522 451 523 452 524 453 525 454 526 455 527 456 528 457 530 458 531 459 532 460 533 461 534 462 535 463 536 464 537 465 539 466 540 467 541 468 542 469 543 470 544 471 545 472 547 473 548 474 549 475 550 476 551 477 552 478 553 479 555 480 556 481 557 482 558 483 559 484 560 485 561 486 562 487 564 488 565 489 566 490 567 491 568 492 569 493 570 494 572 495 573 496 574 497 575 498 576 499 577 500 578 501 579 502 581 503 582 504 583 505 584 506 585 507 586 508 587 509 589 510 590 511 591 512 592 513 593 514 594 515 595 516 596 517 598 518 599 519 600 520 601 521 602 522 603 523 604 524 606 525 607 526 608 527 609 528 610 529 611 530 612 531 613 532 615 533 616 534 617 535 618 536 619 537 620 538 621 539 623 540 624 541 625 542 626 543 627 544 628 545 629 546 630 547 632 548 633 549 634 550 635 551 636 552 637 553 638 554 640 555 641 556 642 557 643 558 644 559 645 560 646 561 647 562 649 563 650 564 651 565 652 566 653 567 654 568 655 569 657 570 658 571 659 572 660 573 661 574 662 575 663 576 664 577 666 578 667 579 668 580 669 581 670 582 671 583 672 584 673 585 675 586 676 587 677 588 678 589 679 590 680 591 681 592 683 593 684 594 685 595 686 596 687 597 688 598 689 599 690 600 692 601 693 602 694 603 695 604 696 605 697 606 698 607 700 608 701 609 702 610 703 611 704 612 705 613 706 614 707 615 709 616 710 617 711 618 712 619 713 620 714 621 715 622 716 623 718 624 719 625 720 626 721 627 722 628 723 629 724 630 726 631 727 632 728 633 729 634 730 635 731 636 732 637 733 638 735 639 736 640 737 641 738 642 739 643 740 644 741 645 742 646 744 647 745 648 746 649 747 650 748 651 749 652 750 653 751 654 753 655 754 656 755 657 756 658 757 659 758 660 759 661 761 662 762 663 763 664 764 665 765 666 766 667 767 668 768 669 770 670 771 671 772 672 773 673 774 674 775 675 776 676 777 677 779 678 780 679 781 680 782 681 783 682 784 683 785 684 786 685 788 686 789 687 790 688 791 689 792 690 793 691 794 692 796 693 797 694 798 695 799 696 800 697 801 698 802 699 803 700 805 701 806 702 807 703 808 704 809 705 810 706 811 707 812 708 814 709 815 710 816 711 817 712 818 713 819 714 820 715 821 716 823 717 824 718 825 719 826 720 827 721 828 722 829 723 831 724 832 725 833 726 834 727 835 728 836 729 837 730 838 731 840 732 841 733 842 734 843 735 844 736 845 737 846 738 847 739 849 740 850 741 851 742 852 743 853 744 854 745 855 746 856 747 858 748 859 749 860 750 861 751 862 752 863 753 864 754 865 755 867 756 868 757 869 758 870 759 871 760 872 761 873 762 874 763 876 764 877 765 878 766 879 767 880 768 881 769 882 770 883 771 885 772 886 773 887 774 888 775 889 776 890 777 891 778 893 779 894 780 895 781 896 782 897 783 898 784 899 785 900 786 902 787 903 788 904 789 905 790 906 791 907 792 908 793 909 794 911 795 912 796 913 797 914 798 915 799 916 800 917 801 918 802 920 803 921 804 922 805 923 806 924 807 925 808 926 809 927 810 929 811 930 812 931 813 932 814 933 815 934 816 935 817 936 818 938 819 939 820 940 821 941 822 942 823 943 824 944 825 945 826 947 827 948 828 949 829 950 830 951 831 952 832 953 833 954 834 956 835 957 836 958 837 959 838 960 839 961 840 962 841 963 842 965 843 966 844 967 845 968 846 969 847 970 848 971 849 972 850 974 851 975 852 976 853 977 854 978 855 979 856 980 857 981 858 983 859 984 860 985 861 986 862 987 863 988 864 989 865 990 866 992 867 993 868 994 869 995 870 996 871 997 872 998 873 999 874 1001 875 1002 876 1003 877 1004 878 1005 879 1006 880 1007 881 1008 882 1010 883 1011 884 1012 885 1013 886 1014 887 1015 888 1016 889 1017 890 1019 891 1020 892 1021 893 1022 894 1023 895 1024 896 1025 897 1026 898 1028 899 1029 900 1030 901 1031 902 1032 903 1033 904 1034 905 1035 906 1037 907 1038 908 1039 909 1040 910 1041 911 1042 912 1043 913 1044 914 1046 915 1047 916 1048 917 1049 918 1050 919 1051 920 1052 921 1053 922 1055 923 1056 924 1057 925 1058 926 1059 927 1060 928 1061 929 1062 930 1064 931 1065 932 1066 933 1067 934 1068 935 1069 936 1070 937 1071 938 1073 939 1074 940 1075 941 1076 942 1077 943 1078 944 1079 945 1080 946 1082 947 1083 948 1084 949 1085 950 1086 951 1087 952 1088 953 1089 954 1091 955 1092 956 1093 957 1094 958 1095 959 1096 960 1097 961 1098 962 1100 963 1101 964 1102 965 1103 966 1104 967 1105 968 1106 969 1107 970 1109 971 1110 972 1111 973 1112 974 1113 975 1114 976 1115 977 1116 978 1118 979 1119 980 1120 981 1121 982 1122 983 1123 984 1124 985 1125 986 1126 987 1128 988 1129 989 1130 990 1131 991 1132 992 1133 993 1134 994 1135 995 1137 996 1138 997 1139 998 1140 999 1141 1000 1142