1 1 2 2 3 5 4 3 5 10 6 13 7 4 8 39 9 26 10 29 11 9 12 20 13 75 14 58 15 41 16 6 17 21 18 52 19 147 20 82 21 61 22 7 23 78 24 45 25 116 26 207 27 122 28 85 29 8 30 11 31 150 32 93 33 164 34 291 35 170 36 125 37 81 38 40 39 19 40 294 41 189 42 244 43 411 44 250 45 173 46 18 47 105 48 104 49 35 50 414 51 381 52 340 53 579 54 346 55 209 56 23 57 42 58 165 59 232 60 67 61 582 62 657 63 500 64 819 65 418 66 253 67 12 68 43 69 90 70 213 71 328 72 131 73 822 74 765 75 692 76 927 77 506 78 281 79 17 80 156 81 79 82 186 83 333 84 488 85 259 86 1158 87 873 88 836 89 1155 90 562 91 313 92 14 93 25 94 300 95 83 96 378 97 429 98 680 99 311 100 1638 101 1317 102 1012 103 1635 104 626 105 349 106 15 107 22 108 37 109 588 110 103 111 762 112 669 113 1000 114 359 115 1854 116 1533 117 1124 118 1851 119 698 120 421 121 16 122 27 123 38 124 53 125 828 126 155 127 1314 128 861 129 1384 130 515 131 2310 132 1749 133 1252 134 2307 135 842 136 509 137 153 138 80 139 51 140 70 141 77 142 1164 143 163 144 1530 145 1341 146 1672 147 619 148 3270 149 2457 150 1396 151 2487 152 1018 153 565 154 162 155 309 156 208 157 99 158 134 159 109 160 1644 161 203 162 1746 163 1725 164 2024 165 655 166 3702 167 2637 168 1684 169 2583 170 1130 171 629 172 47 173 210 174 417 175 464 176 195 177 262 178 157 179 2316 180 307 181 2634 182 2685 183 2248 184 715 185 4614 186 3069 187 2036 188 2919 189 1258 190 701 191 36 192 55 193 330 194 465 195 656 196 279 197 518 198 221 199 3276 200 323 201 3066 202 2721 203 2504 204 791 205 4974 206 3501 207 2260 208 3267 209 1402 210 845 211 49 212 84 213 71 214 426 215 621 216 976 217 327 218 622 219 317 220 3708 221 403 222 3498 223 3453 224 2792 225 1027 226 5166 227 4329 228 2516 229 3699 230 1690 231 929 232 46 233 101 234 180 235 91 236 666 237 681 238 1360 239 387 240 718 241 329 242 4620 243 611 244 4914 245 3753 246 3368 247 1235 248 5838 249 4917 250 2804 251 3903 252 1858 253 1021 254 87 255 86 256 169 257 372 258 107 259 858 260 837 261 2000 262 555 263 1030 264 361 265 6540 266 643 267 5274 268 5373 269 4072 270 1307 271 6534 272 5241 273 3380 274 4611 275 2042 276 1133 277 24 278 171 279 158 280 205 281 756 282 139 283 1338 284 933 285 2768 286 651 287 1238 288 445 289 7404 290 803 291 6138 292 5445 293 4520 294 1427 295 7398 296 5277 297 3716 298 4971 299 2266 300 1261 301 73 302 312 303 339 304 166 305 341 306 1524 307 179 308 1722 309 1245 310 3344 311 771 312 1310 313 637 314 9228 315 1199 316 7002 317 6909 318 5032 319 1579 320 7806 321 5745 322 4084 323 5163 324 2522 325 1405 326 34 327 89 328 600 329 675 330 206 331 413 332 2628 333 211 334 2682 335 1365 336 4048 337 1107 338 1430 339 661 340 9948 341 1219 342 8658 343 7509 344 5608 345 2051 346 9222 347 6141 348 4532 349 5835 350 2810 351 1693 352 159 353 50 354 149 355 1176 356 1071 357 310 358 601 359 3060 360 275 361 3450 362 1677 363 4496 364 1299 365 1582 366 725 367 10332 368 1283 369 9834 370 9609 371 6760 372 2467 373 9942 374 6345 375 5044 376 6531 377 3386 378 1861 379 28 380 231 381 74 382 161 383 1656 384 1311 385 326 386 685 387 3492 388 355 389 5370 390 1869 391 5008 392 1539 393 2054 394 893 395 11676 396 1603 397 10482 398 10749 399 7432 400 2611 401 10326 402 7005 403 5620 404 7395 405 3722 406 2045 407 33 408 44 409 315 410 106 411 181 412 2328 413 1347 414 406 415 829 416 5268 417 415 418 5442 419 2493 420 5584 421 2211 422 2470 423 1201 424 13068 425 1703 426 10554 427 10893 428 8168 429 2851 430 11670 431 8661 432 6772 433 7803 434 4090 435 2269 436 30 437 57 438 76 439 459 440 154 441 233 442 3288 443 1671 444 614 445 1205 446 6132 447 419 448 6906 449 2733 450 6736 451 2535 452 2614 453 1277 454 14796 455 2231 456 11490 457 11865 458 9064 459 3155 460 13062 461 9561 462 7444 463 9219 464 4538 465 2525 466 31 467 54 468 69 469 140 470 627 471 218 472 301 473 4632 474 1815 475 646 476 1313 477 6996 478 463 479 7506 480 2889 481 8144 482 2595 483 2854 484 1325 485 15612 486 2395 487 12282 488 13821 489 10088 490 3311 491 14790 492 9837 493 8180 494 9939 495 5050 496 2665 497 32 498 59 499 102 500 117 501 268 502 915 503 314 504 325 505 6552 506 2139 507 806 508 1373 509 9828 510 547 511 10746 512 3357 513 9040 514 3075 515 3158 516 1453 517 18444 518 2435 519 12690 520 15021 521 11240 522 3535 523 15606 524 10017 525 9076 526 10323 527 5330 528 2813 529 177 530 160 531 115 532 198 533 141 534 524 535 1251 536 442 537 365 538 7416 539 2619 540 1222 541 1489 542 10548 543 599 544 10890 545 3741 546 10064 547 4419 548 4102 549 1625 550 19884 551 2563 552 14010 553 19221 554 13544 555 4099 556 18438 557 10485 558 10100 559 10839 560 5626 561 3121 562 306 563 201 564 416 565 151 566 390 567 237 568 1036 569 1359 570 634 571 469 572 9240 573 2691 574 1286 575 1661 576 12276 577 679 578 13818 579 4989 580 11216 581 5067 582 4934 583 1789 584 20652 585 2719 586 17322 587 21501 588 14888 589 4759 590 19878 591 10557 592 10660 593 11667 594 6242 595 3313 596 95 597 618 598 357 599 928 600 167 601 558 602 285 603 1244 604 1623 605 658 606 605 607 13080 608 3339 609 1606 610 1673 611 14004 612 707 613 15018 614 5469 615 13520 616 5187 617 5222 618 2201 619 23340 620 2887 621 19122 622 21789 623 16360 624 4931 625 20646 626 11493 627 11252 628 13059 629 6626 630 3389 631 324 632 119 633 834 634 405 635 1312 636 227 637 654 638 477 639 1436 640 1827 641 722 642 625 643 14808 644 3627 645 2398 646 1897 647 17316 648 827 649 19218 650 5781 651 14864 652 6147 653 5702 654 2405 655 26124 656 3203 657 19674 658 23733 659 18152 660 5219 661 21678 662 12285 663 12484 664 14787 665 6778 666 3725 667 97 668 420 669 187 670 930 671 537 672 1952 673 299 674 774 675 573 676 2060 677 2499 678 890 679 653 680 18456 681 4275 682 2438 683 2233 684 19668 685 835 686 21498 687 6717 688 16336 689 6687 690 6310 691 2489 692 29580 693 3403 694 20034 695 26001 696 20200 697 5287 698 23334 699 12693 700 13252 701 15603 702 7450 703 3905 704 94 705 113 706 660 707 235 708 1242 709 633 710 2720 711 331 712 1110 713 957 714 2476 715 2715 716 1274 717 733 718 19896 719 5007 720 2566 721 2413 722 20964 723 923 724 21786 725 7485 726 18128 727 7215 728 6622 729 2557 730 31212 731 3671 732 20970 733 27645 734 21320 735 5699 736 26118 737 14013 738 13556 739 15999 740 7810 741 4093 742 303 743 110 744 197 745 852 746 371 747 1362 748 717 749 4000 750 451 751 1302 752 1149 753 2620 754 3243 755 1322 756 793 757 20664 758 5235 759 3206 760 2537 761 21108 762 1091 763 23730 764 9981 765 20176 766 8835 767 7070 768 2653 769 36876 770 4247 771 21114 772 27825 773 22504 774 6307 775 29574 776 15129 777 14900 778 17895 779 8186 780 4541 781 72 782 423 783 142 784 229 785 1332 786 467 787 1674 788 813 789 5536 790 595 791 1542 792 1917 793 2860 794 3651 795 1450 796 941 797 23352 798 5379 799 3406 800 2585 801 22980 802 1195 803 27642 804 10941 805 22480 806 9639 807 8198 808 2909 809 39756 810 4459 811 22986 812 30045 813 24968 814 6619 815 31206 816 17325 817 15620 818 18435 819 9082 820 4841 821 137 822 168 823 603 824 182 825 397 826 1716 827 739 828 1866 829 1077 830 6688 831 623 832 2214 833 2301 834 3164 835 4995 836 1786 837 1073 838 26136 839 6375 840 4462 841 2629 842 24564 843 1355 844 30042 845 11073 846 27088 847 9903 848 9518 849 3253 850 41292 851 4787 852 24570 853 35049 854 26504 855 7067 856 31998 857 17985 858 16372 859 19875 860 9682 861 5053 862 98 863 185 864 360 865 843 866 214 867 461 868 2676 869 931 870 2490 871 1269 872 8096 873 659 874 2598 875 2505 876 4108 877 5427 878 2402 879 1213 880 29592 881 6675 882 4790 883 2749 884 25380 885 1411 886 38442 887 11565 888 29776 889 10131 890 9862 891 3581 892 43356 893 4867 894 25386 895 38445 896 27112 897 8195 898 35790 899 19125 900 18164 901 20295 902 10106 903 5209 904 111 905 202 906 277 907 744 908 1203 909 278 910 617 911 3444 912 1303 913 2730 914 1437 915 8992 916 871 917 3078 918 2841 919 4940 920 6483 921 2554 922 1253 923 31224 924 7251 925 4870 926 2981 927 28020 928 1651 929 43002 930 11913 931 32720 932 10371 933 10438 934 4405 935 46668 936 5123 937 28026 938 40257 939 29800 940 8879 941 36870 942 19677 943 19364 944 20643 945 10418 946 5257 947 92 948 219 949 338 950 305 951 1512 952 1683 953 358 954 665 955 5364 956 1475 957 3354 958 1629 959 10016 960 899 961 4422 962 3345 963 5228 964 7299 965 2650 966 1309 967 36888 968 8547 969 5126 970 3325 971 34644 972 1667 973 43578 974 13437 975 36304 976 12291 977 10574 978 4813 979 52236 980 5239 981 30258 982 40809 983 31240 984 9515 985 39750 986 20037 987 20212 988 21675 989 10514 990 5333 991 297 992 172 993 435 994 410 995 373 996 3048 997 2403 998 422 999 721 1000 6900 1001 1855 1002 3738 1003 1857 1004 11168 1005 1187 1006 5070 1007 3537 1008 5708 1009 9987 1010 2906 1011 1361 1012 39768 1013 9591 1014 5438 1015 3349 1016 38244 1017 1843 1018 47466 1019 14973 1020 40400 1021 13371 1022 11398 1023 4981 1024 59148 1025 5255 1026 34650 1027 41913 1028 32744 1029 9859 1030 40590 1031 20973 1032 20836 1033 23331 1034 10666 1035 5629 1036 174 1037 345 1038 316 1039 867 1040 682 1041 409 1042 5256 1043 3363 1044 550 1045 797 1046 10740 1047 1859 1048 4986 1049 1953 1050 13472 1051 1243 1052 5190 1053 3837 1054 6316 1055 10287 1056 3250 1057 1469 1058 41304 1059 10011 1060 5774 1061 3797 1062 39348 1063 2179 1064 52002 1065 15657 1066 42640 1067 13671 1068 12614 1069 5117 1070 62412 1071 5435 1072 35970 1073 42009 1074 36328 1075 10015 1076 41286 1077 21117 1078 21028 1079 26115 1080 11258 1081 5993 1082 175 1083 342 1084 597 1085 332 1086 1239 1087 826 1088 557 1089 6120 1090 4191 1091 710 1092 841 1093 10884 1094 1951 1095 5466 1096 2157 1097 16288 1098 1315 1099 6150 1100 4605 1101 8204 1102 10851 1103 3578 1104 1589 1105 46680 1106 10467 1107 6406 1108 4469 1109 40068 1110 2387 1111 55290 1112 16809 1113 45008 1114 14427 1115 13238 1116 5309 1117 63996 1118 5743 1119 38250 1120 43005 1121 38728 1122 10435 1123 43350 1124 21969 1125 21332 1126 29571 1127 11986 1128 6245 1129 48 1130 215 1131 678 1132 693 1133 412 1134 1383 1135 1202 1136 613 1137 6984 1138 4803 1139 830 1140 925 1141 13812 1142 2351 1143 5778 1144 2541 1145 18080 1146 1487 1147 8838 1148 5013 1149 9868 1150 12963 1151 4402 1152 1657 1153 52248 1154 10755 1155 6806 1156 4705 1157 41940 1158 2455 1159 55650 1160 18993 1161 49936 1162 17667 1163 14134 1164 5821 1165 71580 1166 5771 1167 39354 1168 43581 1169 40424 1170 10571 1171 46662 1172 22989 1173 22516 1174 31203 1175 12490 1176 6629 1177 145 1178 624 1179 347 1180 1350 1181 1197 1182 620 1183 1731 1184 1370 1185 749 1186 10536 1187 6723 1188 838 1189 1237 1190 15012 1191 2603 1192 6714 1193 2769 1194 20128 1195 1655 1196 10134 1197 5289 1198 10444 1199 13335 1200 4810 1201 1705 1202 59160 1203 11943 1204 7342 1205 4829 1206 42228 1207 2663 1208 60090 1209 19965 1210 53008 1211 19275 1212 16390 1213 6509 1214 73740 1215 5911 1216 40074 1217 47469 1218 41672 1219 11395 1220 52230 1221 24573 1222 23972 1223 31995 1224 13258 1225 6781 1226 146 1227 217 1228 1200 1229 427 1230 2142 1231 1389 1232 652 1233 2199 1234 1658 1235 821 1236 12264 1237 7431 1238 926 1239 1333 1240 21492 1241 2767 1242 7482 1243 2877 1244 22432 1245 1739 1246 10374 1247 5481 1248 11404 1249 14595 1250 4978 1251 1885 1252 62424 1253 12747 1254 8494 1255 5009 1256 45972 1257 2707 1258 70098 1259 20073 1260 54224 1261 19803 1262 17758 1263 6689 1264 79500 1265 6403 1266 41946 1267 52005 1268 42056 1269 12611 1270 59142 1271 25389 1272 24980 1273 33327 1274 13562 1275 7453 1276 135 1277 178 1278 293 1279 2352 1280 535 1281 2622 1282 2397 1283 812 1284 2475 1285 2410 1286 1117 1287 13992 1288 8379 1289 1094 1290 1445 1291 21780 1292 2947 1293 9978 1294 3261 1295 27040 1296 1795 1297 12294 1298 5685 1299 12620 1300 18279 1301 5114 1302 2149 1303 73752 1304 13347 1305 8918 1306 5077 1307 49140 1308 2819 1309 76890 1310 20913 1311 59600 1312 20259 1313 19030 1314 7165 1315 81180 1316 6803 1317 42234 1318 55293 1319 42664 1320 13235 1321 62406 1322 26793 1323 26516 1324 34383 1325 14906 1326 7813 1327 68 1328 267 1329 298 1330 437 1331 3312 1332 647 1333 2694 1334 2781 1335 1228 1336 2631 1337 2626 1338 1229 1339 19656 1340 8991 1341 1198 1342 1597 1343 27636 1344 3287 1345 10938 1346 3369 1347 29728 1348 2279 1349 13374 1350 6693 1351 13244 1352 19407 1353 5306 1354 2429 1355 79512 1356 14499 1357 9574 1358 5173 1359 50772 1360 3299 1361 80514 1362 21273 1363 62480 1364 20739 1365 19718 1366 7633 1367 82572 1368 6967 1369 43938 1370 55653 1371 45032 1372 13639 1373 63990 1374 28029 1375 27124 1376 35787 1377 15626 1378 8189 1379 1257 1380 100 1381 531 1382 322 1383 589 1384 4656 1385 691 1386 3342 1387 4797 1388 1292 1389 2763 1390 2746 1391 1249 1392 21096 1393 9603 1394 1358 1395 1685 1396 30036 1397 3367 1398 11562 1399 3717 1400 32672 1401 2371 1402 14430 1403 7077 1404 14140 1405 19911 1406 5818 1407 2509 1408 82584 1409 17091 1410 9734 1411 5261 1412 56052 1413 3331 1414 81618 1415 21753 1416 65488 1417 24579 1418 20030 1419 8585 1420 86700 1421 7339 1422 45978 1423 60093 1424 47944 1425 14131 1426 66654 1427 30261 1428 29812 1429 36867 1430 16378 1431 8537 1432 318 1433 1305 1434 148 1435 663 1436 362 1437 833 1438 6576 1439 719 1440 3630 1441 5565 1442 1612 1443 3459 1444 2978 1445 1321 1446 24552 1447 10191 1448 1414 1449 1853 1450 38436 1451 3707 1452 13434 1453 3909 1454 36256 1455 2483 1456 17670 1457 7677 1458 16396 1459 19971 1460 6506 1461 2621 1462 86712 1463 19179 1464 10246 1465 5501 1466 60516 1467 3683 1468 83826 1469 21885 1470 72656 1471 26739 1472 20870 1473 8813 1474 93324 1475 8491 1476 49146 1477 62745 1478 49960 1479 14567 1480 68766 1481 31545 1482 31252 1483 39747 1484 17074 1485 9085 1486 295 1487 462 1488 2517 1489 212 1490 831 1491 466 1492 877 1493 9264 1494 823 1495 4278 1496 9597 1497 2444 1498 4395 1499 3322 1500 1385 1501 28008 1502 10455 1503 1654 1504 2281 1505 42996 1506 3715 1507 14970 1508 4317 1509 40352 1510 2503 1511 19278 1512 9213 1513 19036 1514 20571 1515 7162 1516 2725 1517 93336 1518 20019 1519 10478 1520 5965 1521 69300 1522 4355 1523 84018 1524 22149 1525 77456 1526 27339 1527 21142 1528 9629 1529 104460 1530 8915 1531 50778 1532 70101 1533 53032 1534 16387 1535 71574 1536 34653 1537 32756 1538 40587 1539 18170 1540 9593