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