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