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