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