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