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