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