1 1 2 1 3 1 4 2 5 2 6 3 7 2 8 5 9 5 10 3 11 5 12 7 13 9 14 4 15 9 16 10 17 16 18 5 19 14 20 18 21 14 22 15 23 17 24 25 25 6 26 21 27 34 28 19 29 31 30 27 31 38 32 8 33 31 34 57 35 25 36 59 37 42 38 40 39 56 40 10 41 67 42 44 43 70 44 46 45 91 46 33 47 100 48 64 49 80 50 80 51 12 52 117 53 61 54 52 55 141 56 74 57 140 58 43 59 161 60 93 61 143 62 111 63 15 64 193 65 83 66 120 67 253 68 116 69 167 70 208 71 55 72 172 73 213 74 249 75 132 76 239 77 296 78 152 79 123 80 18 81 306 82 112 83 244 84 426 85 174 86 310 87 300 88 70 89 366 90 363 91 372 92 185 93 299 94 383 95 552 96 205 97 197 98 22 99 467 100 148 101 442 102 685 103 254 104 536 105 424 106 88 107 692 108 592 109 539 110 364 111 254 112 641 113 590 114 203 115 960 116 272 117 303 118 597 119 27 120 691 121 194 122 750 123 811 124 636 125 1060 126 363 127 884 128 457 129 1067 130 589 131 323 132 110 133 1216 134 927 135 765 136 701 137 343 138 1220 139 881 140 514 141 1589 142 357 143 452 144 1064 145 32 146 1000 147 801 148 251 149 1213 150 1591 151 1062 152 1588 153 510 154 1430 155 1399 156 1024 157 1912 158 804 159 506 160 137 161 2029 162 1405 163 1066 164 1253 165 459 166 2157 167 1283 168 1112 169 2524 170 463 171 659 172 1802 173 38 174 1419 175 1807 176 322 177 1887 178 2886 179 1700 180 2321 181 1401 182 703 183 2822 184 2141 185 2031 186 1393 187 3249 188 1083 189 769 190 1871 191 1948 192 169 193 3246 194 2077 195 1460 196 2128 197 605 198 3616 199 3227 200 1832 201 1811 202 2134 203 3875 204 595 205 943 206 2921 207 46 208 2388 209 3516 210 1977 211 3602 212 809 213 410 214 2840 215 4953 216 2630 217 3323 218 2581 219 957 220 5147 221 3191 222 3715 223 3166 224 5285 225 1440 226 1141 227 3806 228 3376 229 207 230 5016 231 3006 232 4238 233 1972 234 3457 235 790 236 5810 237 6023 238 2567 239 2955 240 3799 241 5793 242 2295 243 759 244 1323 245 5753 246 877 247 4571 248 54 249 4906 250 6112 251 2715 252 6623 253 1251 254 518 255 4168 256 8129 257 3961 258 4669 259 4498 260 1285 261 8871 262 4653 263 6419 264 6352 265 8295 266 1894 267 1657 268 7125 269 5590 270 253 271 7539 272 2897 273 4267 274 8747 275 2629 276 5422 277 1024 278 9012 279 4025 280 10600 281 3542 282 4654 283 6404 284 8468 285 5435 286 4882 287 960 288 1830 289 10790 290 2407 291 6953 292 64 293 9256 294 7475 295 10151 296 3677 297 11490 298 1885 299 7998 300 5971 301 649 302 5988 303 12863 304 5833 305 6458 306 7485 307 5791 308 1706 309 14616 310 11526 311 6651 312 4908 313 10597 314 11746 315 12653 316 2468 317 2360 318 12574 319 8921 320 307 321 10399 322 11074 323 5496 324 10842 325 5962 326 16578 327 1966 328 3466 329 8268 330 1314 331 13592 332 9592 333 17798 334 4819 335 7126 336 10340 337 12134 338 11312 339 8705 340 1205 341 2496 342 19063 343 5516 344 10330 345 10329 346 76 347 16436 348 15517 349 16243 350 4921 351 19040 352 2779 353 15399 354 10073 355 809 356 8441 357 19762 358 8417 359 18619 360 8806 361 12000 362 12316 363 2244 364 23207 365 20738 366 9351 367 7858 368 16857 369 20473 370 18844 371 13366 372 3187 373 3311 374 20738 375 21166 376 7023 377 13817 378 371 379 20162 380 15939 381 9825 382 18342 383 8209 384 29547 385 3006 386 4526 387 12309 388 1673 389 20025 390 20071 391 28762 392 6476 393 10655 394 16108 395 17097 396 21587 397 14793 398 1504 399 3363 400 32121 401 11147 402 15030 403 22059 404 89 405 27817 406 29559 407 25221 408 6519 409 30388 410 4014 411 27856 412 16355 413 1002 414 11709 415 29623 416 10700 417 11942 418 36249 419 11859 420 18667 421 23954 422 2924 423 35765 424 6995 425 23722 426 35529 427 12951 428 12215 429 26016 430 17344 431 34067 432 27480 433 28764 434 15840 435 4081 436 4576 437 37444 438 34286 439 16853 440 20875 441 447 442 12347 443 36677 444 22547 445 16734 446 33198 447 29857 448 11159 449 50176 450 4492 451 30389 452 5856 453 17945 454 17286 455 2118 456 28903 457 38488 458 45054 459 8610 460 15599 461 24388 462 23727 463 38693 464 24180 465 1865 466 27004 467 4485 468 52071 469 38055 470 20739 471 21484 472 43078 473 104 474 12774 475 45277 476 52906 477 38188 478 8552 479 47042 480 5704 481 47955 482 14595 483 25741 484 1234 485 16009 486 40044 487 43459 488 4140 489 19565 490 31559 491 16685 492 66169 493 4660 494 15797 495 28313 496 43698 497 3777 498 53758 499 17346 500 51296 501 58496 502 17701 503 18523 504 39156 505 34323 506 54572 507 39362 508 56527 509 27419 510 5189 511 6244 512 64356 513 53829 514 35476 515 30856 516 48551 517 536 518 30786 519 63451 520 31405 521 27408 522 64929 523 47102 524 15001 525 81917 526 6573 527 56186 528 7513 529 25703 530 28515 531 2661 532 40989 533 69268 534 68761 535 34114 536 11334 537 22435 538 72264 539 21709 540 36052 541 32491 542 66032 543 38290 544 2300 545 53946 546 5922 547 81799 548 66380 549 36332 550 30227 551 78851 552 122 553 20137 554 71380 555 90182 556 56564 557 63748 558 11119 559 70994 560 7983 561 68937 562 79305 563 41939 564 32106 565 39473 566 1513 567 21612 568 74423 569 62592 570 12205 571 34018 572 52183 573 22998 574 114830 575 7050 576 20832 577 42004 578 75791 579 4844 580 79067 581 37593 582 101247 583 93225 584 23914 585 27481 586 57659 587 63613 588 84762 589 55486 590 104008 591 45591 592 6552 593 8429 594 106261 595 82325 596 21369 597 68383 598 44765 599 97349 600 640 601 67030 602 105388 603 43150 604 43483 605 118978 606 72381 607 19958 608 129502 609 9453 610 60850 611 98671 612 9569 613 36228 614 45543 615 3324 616 57226 617 118642 618 102597 619 75856 620 36497 621 14784 622 31754 623 134731 624 54451 625 52197 626 43972 627 108280 628 59046 629 2823 630 100775 631 7748 632 125158 633 44614 634 114179 635 111125 636 60727 637 41934 638 137182 639 142 640 30937 641 109574 642 69591 643 147724 644 82218 645 128559 646 48276 647 14345 648 104803 649 11023 650 120607 651 126908 652 91174 653 64337 654 59173 655 1846 656 79569 657 28853 658 131290 659 88683 660 29505 661 56788 662 129977 663 83528 664 60993 665 31325 666 191263 667 10439 668 105928 669 27219 670 61150 671 47732 672 126183 673 6168 674 114139 675 74313 676 186984 677 144583 678 31966 679 40021 680 83321 681 111953 682 128299 683 77115 684 181771 685 73352 686 8221 687 110351 688 11258 689 169791 690 123077 691 39956 692 117708 693 123614 694 63875 695 182427 696 762 697 32160 698 133066 699 169290 700 58576 701 67165 702 207185 703 108716 704 26302 705 199290 706 13383 707 135891 708 166204 709 12102 710 50348 711 72761 712 70801 713 4132 714 78798 715 140995 716 195185 717 150133 718 38043 719 153439 720 64630 721 87547 722 19128 723 44311 724 238365 725 10792 726 119162 727 74231 728 58873 729 171846 730 88974 731 110046 732 3448 733 178599 734 10058 735 187184 736 99843 737 231178 738 179862 739 97666 740 57460 741 229024 742 165 743 46468 744 164371 745 131786 746 234243 747 40043 748 117523 749 242070 750 81539 751 18369 752 151796 753 15045 754 202446 755 197563 756 180802 757 120521 758 86992 759 199803 760 2242 761 178817 762 38128 763 222036 764 123840 765 62505 766 91690 767 243189 768 130109 769 125084 770 42204 771 308025 772 15183 773 189366 774 35273 775 87538 776 77280 777 203140 778 7802 779 162062 780 137407 781 327873 782 219015 783 173587 784 42314 785 57323 786 256011 787 118418 788 188941 789 141485 790 189914 791 105841 792 304693 793 114795 794 10257 795 210543 796 14895 797 263947 798 180438 799 70903 800 200077 801 212552 802 89809 803 324230 804 904 805 50010 806 246942 807 264438 808 90300 809 78650 810 101367 811 346152 812 160116 813 265273 814 34372 815 299640 816 70843 817 18682 818 214461 819 275957 820 270534 821 15208 822 203919 823 69107 824 149673 825 107514 826 5107 827 107182 828 253128 829 310688 830 215945 831 96025 832 289695 833 109729 834 142035 835 24562 836 61067 837 404170 838 16158 839 237628 840 103904 841 78052 842 265379 843 131438 844 226442 845 4192 846 303319 847 12958 848 274499 849 203049 850 436788 851 283005 852 152237 853 77851 854 369637 855 192 856 68461 857 241713 858 236530 859 361453 860 104237 861 165513 862 432035 863 133106 864 23362 865 216194 866 20313 867 328471 868 300319 869 76209 870 335245 871 214128 872 125703 873 382319 874 2712 875 365056 876 49915 877 362689 878 170723 879 121141 880 143961 881 431608 882 197939 883 239181 884 56296 885 482270 886 118927 887 21723 888 312189 889 324268 890 45360 891 123457 892 121672 893 317962 894 9813 895 144517 896 226757 897 241174 898 551237 899 325088 900 360144 901 116380 902 55525 903 80903 904 460856 905 165834 906 308087 907 319428 908 275754 909 143624 910 493523 911 175405 912 12728 913 213036 914 380388 915 19544 916 400694 917 229820 918 259990 919 120607 920 478758 921 328457 922 350900 923 124635 924 552069 925 1069 926 75980 927 434847 928 403227 929 207315 930 254423 931 104551 932 149962 933 559023 934 231751 935 509868 936 139730 937 44564 938 441562 939 185368 940 25764 941 365450 942 522778 943 427886 944 19001 945 414634 946 93780 947 286980 948 21147 949 159996 950 6282 951 413191 952 144181 953 435083 954 481072 955 305901 956 211290 957 518296 958 179974 959 463620 960 224045 961 31319 962 262563 963 83204 964 661776 965 23744 966 344083 967 442705 968 143412 969 102569 970 400284 971 190787 972 434263 973 5076 974 126712 975 497389 976 16578 977 395611 978 385096 979 781955 980 434569 981 231164 982 104399 983 579895 984 222 985 99146 986 349261 987 406489 988 544811 989 235654 990 169736 991 230049 992 738370 993 211155 994 29530 995 303361 996 409384 997 27154 998 517975 999 447233 1000 124997 1001 137711 1002 344918 1003 589934 1004 364499 1005 178873 1006 692559 1007 3268 1008 78652 1009 694670 1010 64801 1011 575454 1012 232629 1013 220000 1014 220631 1015 733907 1016 295064 1017 432987 1018 74424 1019 736964 1020 274635 1021 30633 1022 650031 1023 535958 1024 57921 1025 171829 1026 315118 1027 186988 1028 485764 1029 12272 1030 279573 1031 313175 1032 405818 1033 461783 1034 895286 1035 473956 1036 250933 1037 695559 1038 200674 1039 233343 1040 72272 1041 112704 1042 794075 1043 229215 1044 24447 1045 488066 1046 654790 1047 393642 1048 192882 1049 776742 1050 262545 1051 476785 1052 15714 1053 493832 1054 657607 1055 25439 1056 595941 1057 479180 1058 368907 1059 198144 1060 923114 1061 523703 1062 560306 1063 170932 1064 907434 1065 1261 1066 113156 1067 733866 1068 602169 1069 431387 1070 464750 1071 137731 1072 217971 1073 877451 1074 280924 1075 330296 1076 927215 1077 231185 1078 57359 1079 639280 1080 420948 1081 35132 1082 601318 1083 938153 1084 660212 1085 408541 1086 23610 1087 786285 1088 125951 1089 520792 1090 66491 1091 233882 1092 745416 1093 7695 1094 864558 1095 191998 1096 721503 1097 380625 1098 727405 1099 427489 1100 423345 1101 887783 1102 286740 1103 837043 1104 344916 1105 39682 1106 512627 1107 112191 1108 1052276 1109 34312 1110 598148 1111 782276 1112 195498 1113 133686 1114 591594 1115 272645 1116 788225 1117 6122 1118 201871 1119 791997 1120 21077 1121 561445 1122 691704 1123 1340102 1124 653380 1125 343173 1126 764226 1127 138704 1128 887808 1129 256 1130 141408 1131 842879 1132 496864 1133 674052 1134 741195 1135 804685 1136 483520 1137 358217 1138 315958 1139 1217674 1140 326789 1141 37108 1142 420074 1143 752547 1144 35980 1145 796996 1146 654044 1147 328866 1148 238207 1149 573721 1150 994980 1151 598995 1152 251093 1153 1200154 1154 3923 1155 120780 1156 1251511 1157 83473 1158 890461 1159 489483 1160 313636 1161 379831 1162 331150 1163 1204774 1164 432005 1165 998297 1166 749885 1167 97574 1168 1102746 1169 574281 1170 501910 1171 42655 1172 631500 1173 1259362 1174 859890 1175 73484 1176 862041 1177 236304 1178 616872 1179 281424 1180 726726 1181 15267 1182 511624 1183 427465 1184 659570 1185 805600 1186 1412532 1187 680082 1188 569309 1189 1270401 1190 333902 1191 372413 1192 93368 1193 155154 1194 1319779 1195 313093 1196 36280 1197 754193 1198 148257 1199 1250447 1200 553529 1201 256615 1202 1192669 1203 385870 1204 933395 1205 19310 1206 1036248 1207 1096298 1208 32871 1209 870442 1210 929336 1211 516354 1212 316173 1213 1683506 1214 814276 1215 870038 1216 231912 1217 1448025 1218 1483 1219 165564 1220 1195947 1221 737375 1222 882906 1223 835339 1224 811807 1225 179934 1226 311889 1227 1343937 1228 654767 1229 464328 1230 1612375 1231 371378 1232 73340 1233 911111 1234 867172 1235 47415 1236 960756 1237 1611356 1238 997101 1239 868975 1240 253009 1241 29186 1242 1412235 1243 167587 1244 903988 1245 168938 1246 336500 1247 1373652 1248 136771 1249 9383 1250 1681963 1251 253344 1252 1161020 1253 885987 1254 1077483 1255 590128 1256 791924 1257 1467114 1258 445551 1259 1446090 1260 519955 1261 49978 1262 945790 1263 149863 1264 1631562 1265 651887 1266 48845 1267 1383917 1268 1002587 1269 1324311 1270 263518 1271 172933 1272 858795 1273 384259 1274 1368410 1275 7356 1276 313715 1277 1229618 1278 26637 1279 551280 1280 785950 1281 1188990 1282 2215589 1283 964281 1284 499604 1285 1506159 1286 351010 1287 182709 1288 1330800 1289 296 1290 198973 1291 1473840 1292 697117 1293 1084689 1294 1556702 1295 1167452 1296 924054 1297 702721 1298 429260 1299 1948879 1300 495060 1301 328308 1302 46376 1303 1176293 1304 574781 1305 1321982 1306 47282 1307 1200540 1308 1021517 1309 941217 1310 750365 1311 397491 1312 1812781 1313 926068 1314 1620632 1315 243235 1316 955668 1317 563953 1318 348155 1319 2005187 1320 4694 1321 181700 1322 2157105 1323 106758 1324 1348354 1325 1044128 1326 862736 1327 418804 1328 629346 1329 487963 1330 1920155 1331 622476 1332 1846436 1333 387316 1334 1252204 1335 126947 1336 1619825 1337 1116656 1338 1174593 1339 58702 1340 1052683 1341 2306640 1342 1344753 1343 92667 1344 1667774 1345 590422 1346 321444 1347 1140849 1348 220054 1349 415825 1350 1067322 1351 18902 1352 895161 1353 1849087 1354 577245 1355 1041279 1356 1354543 1357 2173817 1358 962115 1359 1172038 1360 2217925 1361 539174 1362 1535137 1363 579703 1364 119799 1365 1019757 1366 211295 1367 2128105 1368 423087 1369 52921 1370 1140622 1371 272781 1372 1054415 1373 2259956 1374 768002 1375 338464 1376 1792564 1377 558011 1378 1726342 1379 23624 1380 325184 1381 2021120 1382 1772738 1383 42197 1384 1251148 1385 1703611 1386 713872 1387 491974 1388 2935068 1389 1238808 1390 1318951 1391 311586 1392 2252605 1393 1739 1394 238459 1395 1892687 1396 1573577 1397 1273604 1398 1529320 1399 1366704 1400 233269 1401 440098 1402 2015239 1403 1380337 1404 773424 1405 644699 1406 2702254 1407 581597 1408 93190 1409 1280495 1410 1405453 1411 1663050 1412 63403 1413 1496692 1414 2669514 1415 1477755 1416 894873 1417 1716168 1418 444410 1419 35908 1420 966056 1421 2427361 1422 221062 1423 1512668 1424 373832 1425 477353 1426 2418520 1427 370925 1428 11396 1429 187355 1430 3091915 1431 331482 1432 1820600 1433 1866064 1434 1567409 1435 805613 1436 1404426 1437 2352615 1438 677492 1439 2409253 1440 1026961 1441 769425 1442 62595 1443 1666979 1444 198452 1445 2475129 1446 1396845 1447 68627 1448 407287 1449 2735390 1450 1629777 1451 2164266 1452 351581 1453 222158 1454 1227017 1455 534817 1456 2290097 1457 1230327 1458 8809 1459 477155 1460 1867702 1461 431636 1462 33476 1463 1026625 1464 1086704 1465 1971067 1466 1424870 1467 3554175 1468 783276 1469 1399835 1470 714931 1471 1326905 1472 2802235 1473 591870 1474 600927 1475 238776 1476 1958056 1477 340 1478 276555 1479 2483387 1480 965929 1481 54344 1482 1701017 1483 3038464 1484 1667122 1485 1671044 1486 1302078 1487 577475 1488 3040004 1489 735981 1490 781735 1491 1861506 1492 57667 1493 2528655 1494 777963 1495 2236970 1496 61660 1497 1774876 1498 2021130 1499 1335198 1500 1552260 1501 643546