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