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