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