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