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