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