1 1 2 2 3 3 4 4 5 1 6 4 7 3 8 8 9 3 10 6 11 9 12 10 13 12 14 11 15 19 16 15 17 26 18 1 19 13 20 39 21 4 22 25 23 47 24 5 25 19 26 70 27 12 28 29 29 89 30 17 31 33 32 115 33 28 34 42 35 148 36 41 37 39 38 189 39 69 40 62 41 235 42 88 43 55 44 294 45 141 46 81 47 362 48 183 49 1 50 84 51 450 52 253 53 5 54 103 55 558 56 333 57 8 58 105 59 669 60 464 61 17 62 153 63 817 64 576 65 29 66 146 67 980 68 790 69 42 70 185 71 1197 72 990 73 64 74 203 75 1421 76 1280 77 106 78 253 79 1709 80 1612 81 144 82 257 83 2012 84 2084 85 212 86 344 87 2429 88 2528 89 303 90 341 91 2836 92 3245 93 420 94 432 95 3380 96 3971 97 566 98 463 99 3961 100 4925 101 794 102 552 103 4699 104 6012 105 1047 106 594 107 5433 108 7434 109 1421 110 1 111 747 112 6457 113 8912 114 1855 115 6 116 761 117 7433 118 11012 119 2419 120 12 121 920 122 8770 123 13174 124 3127 125 24 126 1003 127 10109 128 15971 129 4054 130 48 131 1200 132 11818 133 19107 134 5145 135 68 136 1261 137 13547 138 23102 139 6564 140 109 141 1537 142 15912 143 27266 144 8285 145 174 146 1611 147 18109 148 32872 149 10422 150 247 151 1921 152 21105 153 38779 154 13018 155 352 156 2089 157 24121 158 46152 159 16250 160 522 161 2410 162 27959 163 54400 164 20082 165 707 166 2591 167 31736 168 64581 169 24876 170 970 171 3095 172 36840 173 75480 174 30495 175 1363 176 3270 177 41670 178 89325 179 37480 180 1780 181 3815 182 48114 183 104237 184 45648 185 2412 186 4138 187 54540 188 122417 189 55622 190 3226 191 4769 192 62641 193 142613 194 67360 195 4206 196 5121 197 70680 198 167010 199 81683 200 5437 201 5972 202 81313 203 193514 204 98130 205 7226 206 6394 207 91432 208 225928 209 118389 210 9133 211 7367 212 104656 213 261352 214 141643 215 11804 216 1 217 7974 218 117925 219 303531 220 169683 221 15034 222 7 223 9066 224 134455 225 350468 226 202126 227 19088 228 17 229 9793 230 150900 231 405929 232 241294 233 23870 234 34 235 11305 236 172141 237 466948 238 285605 239 30394 240 74 241 12077 242 192728 243 539453 244 339668 245 37466 246 113 247 13736 248 219024 249 619390 250 400833 251 46987 252 186 253 14940 254 245462 255 712750 256 473953 257 58104 258 290 259 16876 260 277998 261 816902 262 557485 263 71928 264 441 265 18222 266 310717 267 937781 268 657227 269 87993 270 618 271 20689 272 352047 273 1071714 274 769279 275 108856 276 935 277 22251 278 392485 279 1227656 280 904001 281 132037 282 1259 283 25130 284 443211 285 1400431 286 1055472 287 161700 288 1791 289 27237 290 494581 291 1599394 292 1234667 293 196045 294 2421 295 30554 296 556923 297 1821432 298 1437535 299 238225 300 3299 301 32993 302 620002 303 2075811 304 1677298 305 286765 306 4336 307 37227 308 698113 309 2358584 310 1945501 311 347389 312 5969 313 40027 314 775727 315 2682689 316 2263752 317 415883 318 7611 319 44808 320 871109 321 3043049 322 2619920 323 500496 324 10118 325 48621 326 968341 327 3452995 328 3037247 329 598046 330 13014 331 54172 332 1084820 333 3910604 334 3507175 335 715307 336 17013 337 58517 338 1203568 339 4429161 340 4056683 341 850533 342 21401 343 65407 344 1348099 345 5006572 346 4669685 347 1014526 348 27875 349 70489 350 1493123 351 5660731 352 5388609 353 1200926 354 34772 355 78544 356 1668582 357 6388557 358 6191007 359 1425283 360 44503 361 84959 362 1848530 363 7209496 364 7122405 365 1683448 366 55489 367 94126 368 2061532 369 8124698 370 8166722 371 1989067 372 70110 373 101699 374 2280059 375 9153223 376 9376676 377 2340305 378 86507 379 113098 380 2541904 381 10298256 382 10724181 383 2757200 384 109020 385 1 386 121834 387 2807362 388 11584441 389 12287241 390 3233054 391 133417 392 8 393 134796 394 3123712 395 13015041 396 14028573 397 3794777 398 166040 399 23 400 145837 401 3449884 402 14616519 403 16033049 404 4439374 405 202962 406 48 407 160973 408 3831892 409 16399168 410 18273633 411 5191629 412 250705 413 109 414 173683 415 4226057 416 18390096 417 20846728 418 6055188 419 303989 420 184 421 192032 422 4692055 423 20603964 424 23707731 425 7064351 426 373734 427 306 428 206872 429 5168220 430 23073364 431 26997417 432 8215094 433 450896 434 496 435 227997 436 5728538 437 25816615 438 30655758 439 9554037 440 550087 441 775 442 246263 443 6309016 444 28870803 445 34833893 446 11087009 447 662089 448 1104 449 270560 450 6982333 451 32263504 452 39491632 453 12857598 454 802412 455 1681 456 291932 457 7680479 458 36032059 459 44801956 460 14881967 461 960690 462 2336 463 321273 464 8496035 465 40215728 466 50698592 467 17218917 468 1160442 469 3317 470 345857 471 9335049 472 44858057 473 57422982 474 19881204 475 1383243 476 4538 477 379549 478 10311393 479 50006224 480 64887615 481 22946567 482 1660502 483 6286 484 409645 485 11327172 486 55709864 487 73358594 488 26441243 489 1975104 490 8253 491 448674 492 12495506 493 62031743 494 82779021 495 30443033 496 2359966 497 11349 498 483331 499 13711359 500 69025581 501 93448093 502 35003175 503 2794875 504 14712 505 529671 506 15117510 507 76772948 508 105276342 509 40220716 510 3328700 511 19492 512 570079 513 16572196 514 85331627 515 118674931 516 46146144 517 3928806 518 25167 519 623559 520 18248743 521 94803419 522 133523842 523 52910844 524 4657944 525 33014 526 672117 527 19999038 528 105257952 529 150273278 530 60596083 531 5485566 532 41675 533 733382 534 21996149 535 116819790 536 168857900 537 69336680 538 6478317 539 54118 540 789641 541 24082491 542 129560748 543 189790480 544 79254721 545 7603381 546 67927 547 862563 548 26473698 549 143644826 550 212957238 551 90522822 552 8954962 553 86735 554 927407 555 28958618 556 159149158 557 239044931 558 103278231 559 10479574 560 108321 561 1011038 562 31798232 563 176271505 564 267901789 565 117747204 566 12297063 567 136915 568 1088507 569 34771536 570 195104201 571 300294312 572 134114399 573 14361156 574 169092 575 1184837 576 38141239 577 215884285 578 336153467 579 152627079 580 16798607 581 212642 582 1274119 583 41671325 584 238714523 585 376342882 586 173550463 587 19562194 588 261122 589 1387147 590 45685134 591 263895758 592 420741980 593 197188862 594 22827462 595 324322 596 1490636 597 49873377 598 291527604 599 470489061 600 223851185 601 26515627 602 396961 603 1620456 604 54622847 605 321977326 606 525421000 607 253926451 608 30850018 609 490150 610 1742532 611 59608167 612 355373977 613 586801281 614 287823088 615 35765901 616 595130 617 1891372 618 65223205 619 392142518 620 654603520 621 325982199 622 41500368 623 730961 624 2032334 625 71120650 626 432423194 627 730271758 628 368940018 629 47996755 630 883956 631 2206978 632 77779858 633 476755590 634 813714338 635 417240061 636 55575363 637 1077371 638 1 639 2368813 640 84749150 641 525275804 642 906794653 643 471528251 644 64132528 645 1298843 646 9 647 2568362 648 92600553 649 578629148 650 1009381456 651 532493204 652 74073663 653 1574496 654 30 655 2759089 656 100860280 657 636990637 658 1123567785 659 600943984 660 85328921 661 1887478 662 67 663 2988138 664 110111310 665 701107527 666 1249438519 667 677685529 668 98329698 669 2279623 670 156 671 3207232 672 119846731 673 771182763 674 1389369087 675 763766406 676 113031826 677 2723017 678 290 679 3473466 680 130770748 681 848142084 682 1543398657 683 860157392 684 130011498 685 3268356 686 491 687 3725411 688 142236349 689 932164308 690 1714558435 691 968126993 692 149158877 693 3893088 694 834 695 4030420 696 155076388 697 1024366117 698 1902854060 699 1088896792 700 171198600 701 4654893 702 1330 703 4324429 704 168606831 705 1124996245 706 2111697061 707 1224031344 708 196093386 709 5520595 710 1979 711 4673068 712 183685001 713 1235322777 714 2341447112 715 1374983093 716 224624785 717 6576550 718 3014 719 5010689 720 199580841 721 1355629459 722 2596005139 723 1543719513 724 256813297 725 7776221 726 4345 727 5415072 728 217320406 729 1487482898 730 2875706288 731 1731992141 732 293684018 733 9223913 734 6153 735 5802068 736 235978068 737 1631141889 738 3185431252 739 1942205946 740 335183407 741 10878237 742 8645 743 6263226 744 256761908 745 1788467435 746 3525559126 747 2176517763 748 382601559 749 12857673 750 12005 751 6713761 752 278698692 753 1959811878 754 3901611303 755 2437857036 756 436015160 757 15112174 758 16072 759 7240780 760 303032060 761 2147294888 762 4314528279 763 2728822703 764 496830170 765 17810760 766 22040 767 7755777 768 328720249 769 2351341065 770 4770610167 771 3053048699 772 565261633 773 20878261 774 29165 775 8363872 776 357246459 777 2574528846 778 5270865001 779 3413647890 780 643133490 781 24517764 782 38509 783 8953857 784 387306372 785 2817224742 786 5823115566 787 3815052366 788 730572840 789 28673718 790 50434 791 9647992 792 420634234 793 3082497994 794 6428514947 795 4261075504 796 829863316 797 33578115 798 66033 799 10329749 800 455848490 801 3370875520 802 7095939857 803 4757050663 804 941401347 805 39159331 806 84251 807 11119962 808 494750892 809 3685816165 810 7827442142 811 5307619004 812 1067699213 813 45736708 814 109234 815 11899965 816 535870513 817 4027952214 818 8633166878 819 5919323193 820 1209415708 821 53215757 822 138529 823 12809771 824 581330985 825 4401473903 826 9515441053 827 6597659088 828 1369784587 829 61979085 830 175973 831 13699959 832 629304132 833 4806952707 834 10486672973 835 7350630766 836 1549414738 837 71960889 838 221845 839 14734272 840 682263779 841 5249327794 842 11549602826 843 8184907141 844 1752334889 845 83602026 846 279872 847 15760850 848 738283764 849 5729394986 850 12718351902 851 9110071262 852 1979623254 853 96838617 854 347343 855 16938762 856 799938515 857 6252733854 858 13997093783 859 10134242547 860 2235781175 861 112255066 862 435795 863 18108419 864 865163993 865 6820338509 866 15401977260 867 11269051024 868 2522419040 869 129758321 870 538634 871 19458606 872 936989883 873 7438888725 874 16937811991 875 12524116575 876 2845250307 877 150052874 878 666352 879 20792121 880 1012878345 881 8109274399 882 18624221824 883 13913595079 884 3205924842 885 173118080 886 819892 887 22326690 888 1096338205 889 8839364153 890 20466852185 891 15449108272 892 3611516039 893 199773152 894 1009725 895 23857464 896 1184684707 897 9630430241 898 22488041510 899 17147506073 900 4064574825 901 230011345 902 1230159 903 25599611 904 1281585929 905 10491308832 906 24695771651 907 19022923250 908 4573080165 909 264896527 910 1507315 911 27342765 912 1384184970 913 11423561628 914 27115612390 915 21095680150 916 5140542410 917 304428034 918 1829750 919 29334966 920 1496757145 921 12437729761 922 29756869019 923 23382444328 924 5776993455 925 349893042 926 2222043 927 31316315 928 1615807740 929 13535295106 930 32650267154 931 25907904842 932 6486277089 933 401408377 934 2688146 935 33575236 936 1746281742 937 14728581954 938 35806785847 939 28692062903 940 7280752245 941 460487710 942 3251165 943 35844131 944 1884489664 945 16019623265 946 39261519726 947 31764174940 948 8165824817 949 527346979 950 3905033 951 38407254 952 2035611457 953 17422286428 954 43029119176 955 35148555204 956 9155571417 957 603902351 958 4706179 959 40982650 960 2195700674 961 18939116329 962 47149769559 963 38880224855 964 10257208591 965 690429977 966 5635792 967 43902838 968 2370786087 969 20586499277 970 51640633979 971 42987822752 972 11488252812 973 789261106 974 6745786 975 46828033 976 2556095428 977 22366898620 978 56549656913 979 47513739245 980 12856804041 981 900918979 982 8054671 983 50136184 984 2758549889 985 24299442169 986 61897088395 987 52492166004 988 14384304928 989 1028176478 990 9611248 991 53473495 992 2973098870 993 26387496169 994 67737691924 995 57973131921 996 16081717878 997 1171774276 998 11415721 999 1 1000 57216544 1001 3207025031 1002 28652499531 1003 74097622399 1004 63998081292 1005 17973624041 1006 1335176089 1007 13577642 1008 10 1009 61000705 1010 3454958193 1011 31098601645 1012 81039585880 1013 70626661678 1014 20074173475 1015 1519354129 1016 16084359 1017 38 1018 65259342 1019 3725316909 1020 33751070457 1021 88594214679 1022 77907597422 1023 22413694771 1024 1728542239 1025 19036840 1026 92 1027 69545377 1028 4011616225 1029 36614083514 1030 96835899106 1031 85912648134 1032 25008496779 1033 1964142488 1034 22493273 1035 219 1036 74358741 1037 4323516729 1038 39716970396 1039 105800684880 1040 94699830621 1041 27895481484 1042 2231225299 1043 26548538 1044 442 1045 79237658 1046 4654173291 1047 43065252335 1048 115573656737 1049 104353640602 1050 31095855793 1051 2531746588 1052 31238270 1053 774 1054 84678580 1055 5013764017 1056 46691835861 1057 126200174480 1058 114944122832 1059 34652210745 1060 2871939887 1061 36771847 1062 1364 1063 90198447 1064 5394991845 1065 50603578814 1066 137777609305 1067 126571481513 1068 38591560166 1069 3254268803 1070 43168765 1071 2237 1072 96369200 1073 5809587831 1074 54838979559 1075 150359176035 1076 139317969921 1077 42965963091 1078 3686409103 1079 50616530 1080 3480 1081 102614850 1082 6248836261 1083 59405076088 1084 164059691725 1085 153303723344 1086 47806803056 1087 4171664579 1088 59282598 1089 5329 1090 109581554 1091 6726113367 1092 64346469046 1093 178941697211 1094 168626258390 1095 53177107203 1096 4719274893 1097 69347652 1098 7974 1099 116668411 1100 7232204075 1101 69672338650 1102 195136514740 1103 185426581837 1104 59116941766 1105 5333617143 1106 80953149 1107 11424 1108 124528106 1109 7781268331 1110 75432639680 1111 212721321240 1112 203822065141 1113 65699337059 1114 6025956903 1115 94472797 1116 16398 1117 132535703 1118 8363512485 1119 81638587122 1120 231846541846 1121 223979272119 1122 72974379449 1123 6801851985 1124 110049500 1125 22911 1126 141435441 1127 8995173518 1128 88348456578 1129 252602511840 1130 246035842587 1131 81030758439 1132 7675147056 1133 128034013 1134 31464 1135 150473569 1136 9664568094 1137 95574088106 1138 275165752973 1139 270190479643 1140 89927249847 1141 8652923555 1142 148832960 1143 43034 1144 160500948 1145 10390203771 1146 103382684633 1147 299642113969 1148 296606004595 1149 99770640180 1150 9751914552 1151 172787611 1152 58064 1153 170739503 1154 11159774658 1155 111789323931 1156 326233585391 1157 325515075160 1158 110634578255 1159 10981354359 1160 200309251 1161 77019 1162 182038747 1163 11992865574 1164 120869312916 1165 355069009104 1166 357112790641 1167 122643186831 1168 12361500494 1169 232073896 1170 102227 1171 193583406 1172 12876386713 1173 130641060032 1174 386379541781 1175 391672993988 1176 135887654901 1177 13903890947 1178 268528551 1179 134018 1180 206343758 1181 13832737951 1182 141191924896 1183 420315877116 1184 429424168368 1185 150517698749 1186 15633456518 1187 310311448 1188 173569 1189 219358366 1190 14846453294 1191 152541580639 1192 457148063730 1193 470691788772 1194 166640615374 1195 17564584379 1196 358372937 1197 224777 1198 233721660 1199 15942949279 1200 164790616837 1201 497052171160 1202 515745266871 1203 184435975680 1204 19727382665 1205 413373021 1206 288398 1207 248425948 1208 17105878770 1209 177963769604 1210 540337273588 1211 564964697954 1212 204036569739 1213 22140310112 1214 476307004 1215 366906 1216 264581269 1217 18362262936 1218 192173589061 1219 587215191417 1220 618671741259 1221 225651558063 1222 24839624206 1223 548389865 1224 466017 1225 281138049 1226 19694770476 1227 207449911003 1228 638039672101 1229 677312399419 1230 249443537656 1231 27848301599 1232 630782015 1233 588334 1234 299354325 1235 21134170753 1236 223922961772 1237 693057762505 1238 741262896279 1239 275663483352 1240 31210795529 1241 724695428 1242 736420 1243 317984257 1244 22660029146 1245 241625187296 1246 752681178248 1247 811050934777 1248 304503445573 1249 34955271053 1250 832152509 1251 922610 1252 338450488 1253 24307196931 1254 260705972134 1255 817197925510 1256 887119115282 1257 336263014158 1258 39135480708 1259 954439306 1260 1147328 1261 359464137 1262 26054185009 1263 281205395937 1264 887079075543 1265 970082564595 1266 371177188195 1267 43787108436 1268 1093809991 1269 1421130 1270 382455641 1271 27938035774 1272 303290677333 1273 962668024913 1274 1060467536961 1275 409595391738 1276 48974618978 1277 1252490942 1278 1755311 1279 406072423 1280 29935949512 1281 327009967086 1282 1044503605594 1283 1158993519310 1284 451803471769 1285 54742005039 1286 1433125036 1287 2162761 1288 431943519 1289 32090049510 1290 352555956746 1291 1132985402210 1292 1266275251644 1293 498218622104 1294 61168103123 1295 1638009226 1296 2645616 1297 458482689 1298 34373631716 1299 379981359455 1300 1228738592825 1301 1383161103485 1302 549178211548 1303 68306486139 1304 1871323393 1305 3240875 1306 487517539 1307 36834238797 1308 409506838403 1309 1332227764709 1310 1510372206316 1311 605178697370 1312 76252183292 1313 2135637056 1314 3945906