0 1 1 1 2 1 3 1 4 2 5 1 6 1 7 3 8 1 9 2 10 1 11 4 12 2 13 3 14 2 15 1 16 5 17 2 18 5 19 3 20 3 21 1 22 6 23 3 24 8 25 4 26 4 27 4 28 1 29 7 30 3 31 11 32 6 33 6 34 6 35 5 36 1 37 8 38 4 39 14 40 9 41 8 42 10 43 7 44 6 45 1 46 9 47 4 48 19 49 11 50 11 51 14 52 11 53 9 54 8 55 1 56 10 57 5 58 23 59 14 60 15 61 21 62 15 63 14 64 11 65 10 66 1 67 11 68 5 69 28 70 17 71 19 72 28 73 22 74 20 75 17 76 15 77 12 78 1 79 12 80 6 81 34 82 21 83 22 84 40 85 28 86 28 87 24 88 24 89 17 90 15 91 1 92 13 93 6 94 40 95 25 96 27 97 50 98 38 99 37 100 34 101 35 102 27 103 22 104 18 105 1 106 14 107 7 108 46 109 29 110 32 111 65 112 49 113 50 114 43 115 51 116 38 117 35 118 26 119 22 120 1 121 15 122 7 123 54 124 33 125 38 126 79 127 62 128 63 129 59 130 68 131 55 132 50 133 41 134 32 135 27 136 1 137 16 138 8 139 61 140 39 141 43 142 99 143 75 144 82 145 72 146 94 147 72 148 73 149 58 150 51 151 39 152 32 153 1 154 17 155 8 156 69 157 44 158 50 159 118 160 92 161 100 162 92 163 121 164 99 165 96 166 85 167 73 168 62 169 47 170 38 171 1 172 18 173 9 174 78 175 49 176 56 177 145 178 108 179 123 180 115 181 157 182 124 183 132 184 111 185 106 186 89 187 75 188 55 189 46 190 1 191 19 192 9 193 87 194 55 195 63 196 169 197 131 198 146 199 140 200 199 201 161 202 167 203 153 204 139 205 131 206 108 207 88 208 67 209 54 210 1 211 20 212 10 213 96 214 62 215 71 216 200 217 152 218 176 219 164 220 253 221 200 222 218 223 193 224 191 225 174 226 157 227 126 228 107 229 79 230 64 231 1 232 21 233 10 234 107 235 68 236 79 237 231 238 179 239 205 240 199 241 307 242 250 243 272 244 251 245 242 246 242 247 208 248 185 249 154 250 126 251 93 252 76 253 1 254 22 255 11 256 117 257 75 258 87 259 270 260 206 261 241 262 230 263 379 264 305 265 341 266 312 267 314 268 309 269 288 270 245 271 225 272 181 273 149 274 111 275 89 276 1 277 23 278 11 279 128 280 82 281 96 282 307 283 238 284 279 285 269 286 454 287 375 288 412 289 392 290 392 291 406 292 367 293 340 294 299 295 266 296 214 297 178 298 130 299 104 300 1 301 24 302 12 303 140 304 90 305 104 306 354 307 269 308 324 309 311 310 544 311 443 312 515 313 472 314 490 315 511 316 479 317 434 318 415 319 353 320 314 321 257 322 208 323 152 324 122 325 1 326 25 327 12 328 152 329 98 330 115 331 398 332 307 333 368 334 359 335 644 336 529 337 610 338 585 339 593 340 649 341 602 342 570 343 529 344 491 345 416 346 379 347 300 348 244 349 178 350 142 351 1 352 26 353 13 354 164 355 106 356 125 357 453 358 345 359 421 360 405 361 762 362 622 363 732 364 700 365 732 366 793 367 760 368 717 369 692 370 628 371 578 372 505 373 441 374 352 375 286 376 208 377 165 378 1 379 27 380 13 381 178 382 114 383 135 384 506 385 390 386 473 387 467 388 886 389 731 390 861 391 837 392 871 393 992 394 926 395 908 396 874 397 825 398 736 399 706 400 586 401 519 402 413 403 334 404 241 405 192 406 1 407 28 408 14 409 191 410 124 411 145 412 569 413 435 414 535 415 522 416 1036 417 846 418 1020 419 985 420 1049 421 1193 422 1151 423 1108 424 1104 425 1041 426 966 427 908 428 816 429 692 430 608 431 483 432 387 433 281 434 222 435 1 436 29 437 14 438 205 439 133 440 157 441 630 442 486 443 598 444 589 445 1193 446 985 447 1179 448 1166 449 1236 450 1448 451 1381 452 1384 453 1349 454 1320 455 1216 456 1198 457 1046 458 967 459 810 460 713 461 559 462 452 463 325 464 256 465 1 466 30 467 15 468 220 469 142 470 169 471 704 472 536 473 669 474 659 475 1376 476 1126 477 1379 478 1349 479 1460 480 1737 481 1667 482 1662 483 1683 484 1613 485 1541 486 1519 487 1375 488 1242 489 1131 490 952 491 824 492 654 493 523 494 375 495 296 496 1 497 31 498 15 499 235 500 152 501 181 502 775 503 596 504 741 505 734 506 1573 507 1295 508 1578 509 1576 510 1691 511 2077 512 1985 513 2017 514 2025 515 2016 516 1880 517 1936 518 1739 519 1639 520 1452 521 1331 522 1100 523 966 524 757 525 604 526 433 527 340 528 1 529 32 530 16 531 250 532 163 533 193 534 858 535 655 536 825 537 809 538 1794 539 1473 540 1824 541 1806 542 1976 543 2437 544 2374 545 2405 546 2449 547 2429 548 2349 549 2380 550 2209 551 2077 552 1915 553 1713 554 1537 555 1291 556 1119 557 875 558 697 559 499 560 390 561 1 562 33 563 16 564 267 565 173 566 206 567 939 568 721 569 908 570 903 571 2028 572 1675 573 2075 574 2082 575 2265 576 2880 577 2774 578 2878 579 2926 580 2947 581 2822 582 2992 583 2710 584 2646 585 2427 586 2263 587 1976 588 1807 589 1496 590 1294 591 1010 592 804 593 571 594 448 595 1 596 34 597 17 598 283 599 184 600 219 601 1033 602 788 603 1001 604 991 605 2299 606 1886 607 2369 608 2373 609 2613 610 3346 611 3267 612 3385 613 3493 614 3521 615 3423 616 3622 617 3395 618 3255 619 3091 620 2872 621 2608 622 2327 623 2095 624 1732 625 1494 626 1166 627 921 628 657 629 512 630 1 631 35 632 17 633 300 634 195 635 234 636 1124 637 864 638 1095 639 1090 640 2583 641 2132 642 2667 643 2707 644 2977 645 3908 646 3781 647 3998 648 4101 649 4218 650 4082 651 4421 652 4101 653 4090 654 3799 655 3667 656 3309 657 3077 658 2700 659 2427 660 1999 661 1726 662 1335 663 1060 664 751 665 585 666 1 667 36 668 18 669 318 670 207 671 247 672 1231 673 938 674 1201 675 1195 676 2898 677 2384 678 3032 679 3049 680 3394 681 4510 682 4399 683 4641 684 4858 685 4952 686 4884 687 5312 688 4988 689 4951 690 4773 691 4516 692 4218 693 3911 694 3573 695 3130 696 2803 697 2312 698 1977 699 1539 700 1211 701 858 702 668 703 1 704 37 705 18 706 336 707 219 708 262 709 1334 710 1023 711 1307 712 1308 713 3237 714 2669 715 3391 716 3459 717 3828 718 5204 719 5059 720 5418 721 5639 722 5865 723 5728 724 6398 725 5982 726 6041 727 5777 728 5682 729 5192 730 4994 731 4546 732 4146 733 3615 734 3243 735 2649 736 2280 737 1758 738 1385 739 980 740 760 741 1 742 38 743 19 744 354 745 231 746 277 747 1452 748 1107 749 1427 750 1419 751 3613 752 2971 753 3809 754 3878 755 4342 756 5946 757 5821 758 6249 759 6576 760 6835 761 6778 762 7560 763 7183 764 7256 765 7049 766 6890 767 6528 768 6156 769 5812 770 5276 771 4788 772 4189 773 3718 774 3057 775 2606 776 2011 777 1583 778 1116 779 864 780 1 781 39 782 19 783 374 784 243 785 292 786 1567 787 1201 788 1546 789 1552 790 4007 791 3305 792 4241 793 4354 794 4864 795 6822 796 6624 797 7210 798 7593 799 7984 800 7869 801 9004 802 8469 803 8739 804 8470 805 8419 806 7915 807 7751 808 7174 809 6748 810 6097 811 5553 812 4801 813 4294 814 3495 815 2981 816 2300 817 1803 818 1268 819 982 820 1 821 40 822 20 823 393 824 257 825 308 826 1697 827 1294 828 1679 829 1676 830 4450 831 3655 832 4739 833 4851 834 5463 835 7744 836 7576 837 8234 838 8754 839 9225 840 9212 841 10534 842 10055 843 10327 844 10199 845 10131 846 9666 847 9408 848 9044 849 8333 850 7802 851 7076 852 6367 853 5550 854 4909 855 4001 856 3413 857 2621 858 2049 859 1442 860 1113 861 1 862 41 863 20 864 413 865 270 866 325 867 1825 868 1397 869 1812 870 1817 871 4912 872 4049 873 5239 874 5416 875 6090 876 8796 877 8571 878 9445 879 9997 880 10659 881 10624 882 12390 883 11742 884 12297 885 12053 886 12220 887 11630 888 11507 889 10997 890 10507 891 9637 892 9062 893 8117 894 7365 895 6348 896 5622 897 4583 898 3890 899 2979 900 2331 901 1635 902 1260 903 1 904 42 905 21 906 434 907 283 908 341 909 1971 910 1501 911 1957 912 1963 913 5418 914 4454 915 5823 916 5994 917 6800 918 9929 919 9707 920 10716 921 11469 922 12190 923 12272 924 14423 925 13768 926 14385 927 14351 928 14462 929 14017 930 13858 931 13472 932 12779 933 12162 934 11204 935 10400 936 9394 937 8426 938 7272 939 6446 940 5225 941 4423 942 3391 943 2644 944 1851 945 1426 946 1 947 43 948 21 949 455 950 297 951 358 952 2112 953 1616 954 2105 955 2118 956 5955 957 4905 958 6406 959 6656 960 7529 961 11211 962 10920 963 12172 964 13015 965 14002 966 14014 967 16767 968 15976 969 16921 970 16792 971 17246 972 16589 973 16726 974 16256 975 15658 976 14798 977 14147 978 12865 979 12042 980 10754 981 9657 982 8345 983 7349 984 5944 985 5036 986 3847 987 2995 988 2095 989 1610 990 1 991 44 992 22 993 476 994 312 995 375 996 2270 997 1730 998 2268 999 2273 1000 6539 1001 5378 1002 7078 1003 7332 1004 8361 1005 12568 1006 12297 1007 13733 1008 14777 1009 15915 1010 16099 1011 19296 1012 18555 1013 19672 1014 19746 1015 20212 1016 19768 1017 19814 1018 19653 1019 18893 1020 18142 1021 17230 1022 16252 1023 14908 1024 13792 1025 12327 1026 11092 1027 9518 1028 8364 1029 6770 1030 5717 1031 4359 1032 3390 1033 2367 1034 1816 1035 1 1036 45 1037 22 1038 499 1039 326 1040 394 1041 2425 1042 1854 1043 2430 1044 2453 1045 7152 1046 5890 1047 7761 1048 8092 1049 9210 1050 14120 1051 13737 1052 15503 1053 16682 1054 18094 1055 18264 1056 22303 1057 21305 1058 22881 1059 22967 1060 23807 1061 23165 1062 23646 1063 23330 1064 22846 1065 21911 1066 21137 1067 19801 1068 18842 1069 17082 1070 15815 1071 14174 1072 12651 1073 10837 1074 9530 1075 7689 1076 6478 1077 4936 1078 3831 1079 2669 1080 2048 1081 1 1082 46 1083 23 1084 521 1085 341 1086 412 1087 2599 1088 1979 1089 2607 1090 2623 1091 7825 1092 6430 1093 8526 1094 8882 1095 10168 1096 15749 1097 15388 1098 17378 1099 18825 1100 20447 1101 20774 1102 25505 1103 24570 1104 26362 1105 26710 1106 27722 1107 27271 1108 27735 1109 27891 1110 27121 1111 26511 1112 25541 1113 24311 1114 22970 1115 21599 1116 19592 1117 18203 1118 16169 1119 14414 1120 12351 1121 10829 1122 8715 1123 7340 1124 5580 1125 4322 1126 3011 1127 2304 1128 1 1129 47 1130 23 1131 544 1132 356 1133 431 1134 2769 1135 2116 1136 2785 1137 2810 1138 8528 1139 7023 1140 9304 1141 9754 1142 11160 1143 17578 1144 17113 1145 19515 1146 21099 1147 23115 1148 23439 1149 29190 1150 28041 1151 30471 1152 30756 1153 32297 1154 31760 1155 32691 1156 32794 1157 32424 1158 31492 1159 30929 1160 29394 1161 28211 1162 26351 1163 24778 1164 22577 1165 20767 1166 18432 1167 16432 1168 14045 1169 12276 1170 9879 1171 8298 1172 6296 1173 4877 1174 3389 1175 2590 1176 1 1177 48 1178 24 1179 568 1180 372 1181 449 1182 2959 1183 2251 1184 2980 1185 3004 1186 9286 1187 7632 1188 10196 1189 10652 1190 12255 1191 19525 1192 19055 1193 21756 1194 23702 1195 25938 1196 26494 1197 33197 1198 32023 1199 34847 1200 35596 1201 37233 1202 36975 1203 38101 1204 38730 1205 38113 1206 37686 1207 36768 1208 35613 1209 34127 1210 32381 1211 30231 1212 28587 1213 25759 1214 23687 1215 21019 1216 18696 1217 15924 1218 13924 1219 11171 1220 9368 1221 7108 1222 5490 1223 3809 1224 2910 1225 1 1226 49 1227 24 1228 592 1229 388 1230 469 1231 3144 1232 2401 1233 3174 1234 3210 1235 10086 1236 8297 1237 11083 1238 11661 1239 13389 1240 21678 1241 21101 1242 24289 1243 26428 1244 29165 1245 29696 1246 37763 1247 36342 1248 39896 1249 40714 1250 43120 1251 42634 1252 44417 1253 45247 1254 45015 1255 44335 1256 44020 1257 42370 1258 41367 1259 39197 1260 37159 1261 34922 1262 32616 1263 29403 1264 27019 1265 23929 1266 21202 1267 18071 1268 15746 1269 12617 1270 10578 1271 8003 1272 6173 1273 4281 1274 3264 1275 1 1276 50 1277 25 1278 616 1279 404 1280 490 1281 3349 1282 2549 1283 3386 1284 3414 1285 10949 1286 8992 1287 12077 1288 12692 1289 14658 1290 23968 1291 23371 1292 26972 1293 29490 1294 32570 1295 33397 1296 42652 1297 41264 1298 45377 1299 46621 1300 49432 1301 49346 1302 51252 1303 52860 1304 52576 1305 52405 1306 51823 1307 50764 1308 49232 1309 47542 1310 44985 1311 42979 1312 39848 1313 37250 1314 33545 1315 30780 1316 27142 1317 24074 1318 20441 1319 17793 1320 14252 1321 11915 1322 9000 1323 6940 1324 4803 1325 3658