1 1 2 4 3 6 4 8 5 9 6 10 7 13 8 15 9 17 10 18 11 19 12 22 13 24 14 26 15 27 16 28 17 31 18 33 19 35 20 36 21 37 22 39 23 40 24 42 25 44 26 45 27 46 28 48 29 51 30 53 31 54 32 55 33 57 34 59 35 60 36 62 37 63 38 64 39 66 40 68 41 69 42 71 43 72 44 73 45 75 46 77 47 78 48 79 49 80 50 81 51 82 52 84 53 86 54 87 55 88 56 90 57 91 58 93 59 95 60 96 61 97 62 99 63 100 64 103 65 105 66 107 67 108 68 109 69 112 70 114 71 116 72 117 73 118 74 121 75 123 76 125 77 126 78 127 79 129 80 130 81 132 82 134 83 135 84 136 85 138 86 141 87 143 88 144 89 145 90 147 91 149 92 150 93 152 94 153 95 154 96 156 97 158 98 159 99 161 100 162 101 163 102 165 103 167 104 168 105 169 106 170 107 171 108 172 109 174 110 176 111 177 112 178 113 180 114 181 115 183 116 185 117 186 118 187 119 189 120 190 121 192 122 194 123 195 124 196 125 198 126 202 127 204 128 206 129 207 130 208 131 211 132 213 133 215 134 216 135 217 136 219 137 220 138 222 139 224 140 225 141 226 142 228 143 231 144 233 145 234 146 235 147 237 148 239 149 240 150 242 151 243 152 244 153 246 154 248 155 249 156 251 157 252 158 253 159 255 160 257 161 258 162 259 163 260 164 261 165 262 166 264 167 266 168 267 169 268 170 270 171 271 172 273 173 275 174 276 175 277 176 279 177 280 178 282 179 284 180 285 181 286 182 288 183 291 184 293 185 294 186 295 187 297 188 299 189 301 190 303 191 305 192 306 193 307 194 309 195 310 196 312 197 314 198 315 199 316 200 318 201 321 202 323 203 324 204 325 205 327 206 329 207 330 208 332 209 333 210 334 211 336 212 338 213 339 214 341 215 342 216 343 217 345 218 347 219 348 220 349 221 350 222 351 223 352 224 354 225 356 226 357 227 358 228 360 229 361 230 363 231 365 232 366 233 367 234 369 235 370 236 372 237 374 238 375 239 376 240 378 241 381 242 383 243 384 244 385 245 387 246 389 247 390 248 392 249 393 250 394 251 396 252 398 253 399 254 400 255 402 256 404 257 405 258 406 259 408 260 411 261 413 262 414 263 415 264 417 265 419 266 420 267 422 268 423 269 424 270 426 271 428 272 429 273 431 274 432 275 433 276 435 277 437 278 438 279 439 280 440 281 441 282 442 283 444 284 446 285 447 286 448 287 450 288 451 289 453 290 455 291 456 292 457 293 459 294 460 295 462 296 464 297 465 298 466 299 468 300 471 301 473 302 474 303 475 304 477 305 479 306 480 307 482 308 483 309 484 310 486 311 488 312 489 313 491 314 492 315 493 316 495 317 497 318 498 319 499 320 501 321 503 322 504 323 505 324 507 325 509 326 510 327 512 328 513 329 514 330 516 331 518 332 519 333 521 334 522 335 523 336 525 337 527 338 528 339 529 340 530 341 531 342 532 343 534 344 536 345 537 346 538 347 540 348 541 349 543 350 545 351 546 352 547 353 549 354 550 355 552 356 554 357 555 358 556 359 558 360 561 361 563 362 564 363 565 364 567 365 569 366 570 367 572 368 573 369 574 370 576 371 578 372 579 373 581 374 582 375 583 376 585 377 587 378 588 379 589 380 590 381 591 382 592 383 594 384 596 385 597 386 598 387 600 388 602 389 603 390 604 391 606 392 608 393 609 394 611 395 612 396 613 397 615 398 617 399 618 400 619 401 620 402 621 403 622 404 624 405 626 406 627 407 628 408 630 409 631 410 633 411 635 412 636 413 637 414 639 415 640 416 642 417 644 418 645 419 646 420 648 421 651 422 653 423 654 424 655 425 657 426 659 427 660 428 662 429 663 430 664 431 666 432 668 433 669 434 671 435 672 436 673 437 675 438 677 439 678 440 679 441 680 442 681 443 682 444 684 445 686 446 687 447 688 448 690 449 691 450 693 451 695 452 696 453 697 454 699 455 701 456 702 457 703 458 705 459 707 460 708 461 709 462 710 463 711 464 712 465 714 466 716 467 717 468 718 469 720 470 721 471 723 472 725 473 726 474 727 475 729 476 730 477 732 478 734 479 735 480 736 481 738 482 741 483 743 484 744 485 745 486 747 487 749 488 750 489 752 490 753 491 754 492 756 493 758 494 759 495 761 496 762 497 763 498 765 499 767 500 768 501 769 502 770 503 771 504 772 505 774 506 776 507 777 508 778 509 780 510 781 511 783 512 785 513 786 514 787 515 789 516 790 517 792 518 794 519 795 520 796 521 798 522 799 523 800 524 801 525 802 526 804 527 806 528 807 529 808 530 810 531 811 532 813 533 815 534 816 535 817 536 819 537 820 538 822 539 824 540 825 541 826 542 828 543 831 544 833 545 834 546 835 547 837 548 839 549 840 550 842 551 843 552 844 553 846 554 848 555 849 556 851 557 852 558 853 559 855 560 857 561 858 562 859 563 860 564 861 565 862 566 864 567 866 568 867 569 868 570 870 571 871 572 873 573 875 574 876 575 877 576 879 577 880 578 882 579 884 580 885 581 886 582 888 583 889 584 891 585 893 586 894 587 895 588 897 589 898 590 899 591 900 592 901 593 903 594 905 595 906 596 907 597 909 598 910 599 912 600 914 601 915 602 916 603 918 604 921 605 923 606 924 607 925 608 927 609 929 610 930 611 932 612 933 613 934 614 936 615 938 616 939 617 941 618 942 619 943 620 945 621 947 622 948 623 949 624 950 625 951 626 952 627 954 628 956 629 957 630 958 631 960 632 961 633 963 634 965 635 966 636 967 637 969 638 970 639 972 640 974 641 975 642 976 643 978 644 979 645 981 646 983 647 984 648 985 649 987 650 988 651 989 652 990 653 992 654 993 655 994 656 996 657 997 658 998 659 999 660 1000 661 1003 662 1005 663 1007 664 1008 665 1009 666 1012 667 1014 668 1016 669 1017 670 1018 671 1021 672 1023 673 1025 674 1026 675 1027 676 1029 677 1030 678 1032 679 1034 680 1035 681 1036 682 1038 683 1041 684 1043 685 1044 686 1045 687 1047 688 1049 689 1050 690 1052 691 1053 692 1054 693 1056 694 1058 695 1059 696 1061 697 1062 698 1063 699 1065 700 1067 701 1068 702 1069 703 1070 704 1071 705 1072 706 1074 707 1076 708 1077 709 1078 710 1080 711 1081 712 1083 713 1085 714 1086 715 1087 716 1089 717 1090 718 1092 719 1094 720 1095 721 1096 722 1098 723 1102 724 1104 725 1106 726 1107 727 1108 728 1111 729 1113 730 1115 731 1116 732 1117 733 1119 734 1120 735 1122 736 1124 737 1125 738 1126 739 1128 740 1131 741 1133 742 1134 743 1135 744 1137 745 1139 746 1140 747 1142 748 1143 749 1144 750 1146 751 1148 752 1149 753 1151 754 1152 755 1153 756 1155 757 1157 758 1158 759 1159 760 1160 761 1161 762 1162 763 1164 764 1166 765 1167 766 1168 767 1170 768 1171 769 1173 770 1175 771 1176 772 1177 773 1179 774 1180 775 1182 776 1184 777 1185 778 1186 779 1188 780 1191 781 1193 782 1194 783 1195 784 1197 785 1199 786 1201 787 1203 788 1205 789 1206 790 1207 791 1209 792 1210 793 1212 794 1214 795 1215 796 1216 797 1218 798 1221 799 1223 800 1224 801 1225 802 1227 803 1229 804 1230 805 1232 806 1233 807 1234 808 1236 809 1238 810 1239 811 1241 812 1242 813 1243 814 1245 815 1247 816 1248 817 1249 818 1250 819 1251 820 1252 821 1254 822 1256 823 1257 824 1258 825 1260 826 1261 827 1263 828 1265 829 1266 830 1267 831 1269 832 1270 833 1272 834 1274 835 1275 836 1276 837 1278 838 1281 839 1283 840 1284 841 1285 842 1287 843 1289 844 1290 845 1292 846 1293 847 1294 848 1296 849 1298 850 1299 851 1300 852 1302 853 1304 854 1305 855 1306 856 1308 857 1311 858 1313 859 1314 860 1315 861 1317 862 1319 863 1320 864 1322 865 1323 866 1324 867 1326 868 1328 869 1329 870 1331 871 1332 872 1333 873 1335 874 1337 875 1338 876 1339 877 1340 878 1341 879 1342 880 1344 881 1346 882 1347 883 1348 884 1350 885 1351 886 1353 887 1355 888 1356 889 1357 890 1359 891 1360 892 1362 893 1364 894 1365 895 1366 896 1368 897 1371 898 1373 899 1374 900 1375 901 1377 902 1379 903 1380 904 1382 905 1383 906 1384 907 1386 908 1388 909 1389 910 1391 911 1392 912 1393 913 1395 914 1397 915 1398 916 1399 917 1401 918 1403 919 1404 920 1405 921 1407 922 1409 923 1410 924 1412 925 1413 926 1414 927 1416 928 1418 929 1419 930 1421 931 1422 932 1423 933 1425 934 1427 935 1428 936 1429 937 1430 938 1431 939 1432 940 1434 941 1436 942 1437 943 1438 944 1440 945 1441 946 1443 947 1445 948 1446 949 1447 950 1449 951 1450 952 1452 953 1454 954 1455 955 1456 956 1458 957 1461 958 1463 959 1464 960 1465 961 1467 962 1469 963 1470 964 1472 965 1473 966 1474 967 1476 968 1478 969 1479 970 1481 971 1482 972 1483 973 1485 974 1487 975 1488 976 1489 977 1490 978 1491 979 1492 980 1494 981 1496 982 1497 983 1498 984 1500 985 1502 986 1503 987 1504 988 1506 989 1508 990 1509 991 1511 992 1512 993 1513 994 1515 995 1517 996 1518 997 1519 998 1520 999 1521 1000 1522