1 1 2 2 3 3 4 5 5 4 6 9 7 6 8 15 9 7 10 22 11 8 12 30 13 10 14 40 15 11 16 51 17 12 18 63 19 13 20 76 21 14 22 90 23 16 24 106 25 17 26 123 27 18 28 141 29 19 30 160 31 20 32 180 33 21 34 201 35 23 36 224 37 24 38 248 39 25 40 273 41 26 42 299 43 27 44 326 45 28 46 354 47 29 48 383 49 31 50 414 51 32 52 446 53 33 54 479 55 34 56 513 57 35 58 548 59 36 60 584 61 37 62 621 63 38 64 659 65 39 66 698 67 41 68 739 69 42 70 781 71 43 72 824 73 44 74 868 75 45 76 913 77 46 78 959 79 47 80 1006 81 48 82 1054 83 49 84 1103 85 50 86 1153 87 52 88 1205 89 53 90 1258 91 54 92 1312 93 55 94 1367 95 56 96 1423 97 57 98 1480 99 58 100 1538 101 59 102 1597 103 60 104 1657 105 61 106 1718 107 62 108 1780 109 64 110 1844 111 65 112 1909 113 66 114 1975 115 67 116 2042 117 68 118 2110 119 69 120 2179 121 70 122 2249 123 71 124 2320 125 72 126 2392 127 73 128 2465 129 74 130 2539 131 75 132 2614 133 77 134 2691 135 78 136 2769 137 79 138 2848 139 80 140 2928 141 81 142 3009 143 82 144 3091 145 83 146 3174 147 84 148 3258 149 85 150 3343 151 86 152 3429 153 87 154 3516 155 88 156 3604 157 89 158 3693 159 91 160 3784 161 92 162 3876 163 93 164 3969 165 94 166 4063 167 95 168 4158 169 96 170 4254 171 97 172 4351 173 98 174 4449 175 99 176 4548 177 100 178 4648 179 101 180 4749 181 102 182 4851 183 103 184 4954 185 104 186 5058 187 105 188 5163 189 107 190 5270 191 108 192 5378 193 109 194 5487 195 110 196 5597 197 111 198 5708 199 112 200 5820 201 113 202 5933 203 114 204 6047 205 115 206 6162 207 116 208 6278 209 117 210 6395 211 118 212 6513 213 119 214 6632 215 120 216 6752 217 121 218 6873 219 122 220 6995 221 124 222 7119 223 125 224 7244 225 126 226 7370 227 127 228 7497 229 128 230 7625 231 129 232 7754 233 130 234 7884 235 131 236 8015 237 132 238 8147 239 133 240 8280 241 134 242 8414 243 135 244 8549 245 136 246 8685 247 137 248 8822 249 138 250 8960 251 139 252 9099 253 140 254 9239 255 142 256 9381 257 143 258 9524 259 144 260 9668 261 145 262 9813 263 146 264 9959 265 147 266 10106 267 148 268 10254 269 149 270 10403 271 150 272 10553 273 151 274 10704 275 152 276 10856 277 153 278 11009 279 154 280 11163 281 155 282 11318 283 156 284 11474 285 157 286 11631 287 158 288 11789 289 159 290 11948 291 161 292 12109 293 162 294 12271 295 163 296 12434 297 164 298 12598 299 165 300 12763 301 166 302 12929 303 167 304 13096 305 168 306 13264 307 169 308 13433 309 170 310 13603 311 171 312 13774 313 172 314 13946 315 173 316 14119 317 174 318 14293 319 175 320 14468 321 176 322 14644 323 177 324 14821 325 178 326 14999 327 179 328 15178 329 181 330 15359 331 182 332 15541 333 183 334 15724 335 184 336 15908 337 185 338 16093 339 186 340 16279 341 187 342 16466 343 188 344 16654 345 189 346 16843 347 190 348 17033 349 191 350 17224 351 192 352 17416 353 193 354 17609 355 194 356 17803 357 195 358 17998 359 196 360 18194 361 197 362 18391 363 198 364 18589 365 199 366 18788 367 200 368 18988 369 202 370 19190 371 203 372 19393 373 204 374 19597 375 205 376 19802 377 206 378 20008 379 207 380 20215 381 208 382 20423 383 209 384 20632 385 210 386 20842 387 211 388 21053 389 212 390 21265 391 213 392 21478 393 214 394 21692 395 215 396 21907 397 216 398 22123 399 217 400 22340 401 218 402 22558 403 219 404 22777 405 220 406 22997 407 221 408 23218 409 222 410 23440 411 223 412 23663 413 225 414 23888 415 226 416 24114 417 227 418 24341 419 228 420 24569 421 229 422 24798 423 230 424 25028 425 231 426 25259 427 232 428 25491 429 233 430 25724 431 234 432 25958 433 235 434 26193 435 236 436 26429 437 237 438 26666 439 238 440 26904 441 239 442 27143 443 240 444 27383 445 241 446 27624 447 242 448 27866 449 243 450 28109 451 244 452 28353 453 245 454 28598 455 246 456 28844 457 247 458 29091 459 249 460 29340 461 250 462 29590 463 251 464 29841 465 252 466 30093 467 253 468 30346 469 254 470 30600 471 255 472 30855 473 256 474 31111 475 257 476 31368 477 258 478 31626 479 259 480 31885 481 260 482 32145 483 261 484 32406 485 262 486 32668 487 263 488 32931 489 264 490 33195 491 265 492 33460 493 266 494 33726 495 267 496 33993 497 268 498 34261 499 269 500 34530 501 270 502 34800 503 271 504 35071 505 272 506 35343 507 274 508 35617 509 275 510 35892 511 276 512 36168 513 277 514 36445 515 278 516 36723 517 279 518 37002 519 280 520 37282 521 281 522 37563 523 282 524 37845 525 283 526 38128 527 284 528 38412 529 285 530 38697 531 286 532 38983 533 287 534 39270 535 288 536 39558 537 289 538 39847 539 290 540 40137 541 291 542 40428 543 292 544 40720 545 293 546 41013 547 294 548 41307 549 295 550 41602 551 296 552 41898 553 297 554 42195 555 298 556 42493 557 300 558 42793 559 301 560 43094 561 302 562 43396 563 303 564 43699 565 304 566 44003 567 305 568 44308 569 306 570 44614 571 307 572 44921 573 308 574 45229 575 309 576 45538 577 310 578 45848 579 311 580 46159 581 312 582 46471 583 313 584 46784 585 314 586 47098 587 315 588 47413 589 316 590 47729 591 317 592 48046 593 318 594 48364 595 319 596 48683 597 320 598 49003 599 321 600 49324 601 322 602 49646 603 323 604 49969 605 324 606 50293 607 325 608 50618 609 327 610 50945 611 328 612 51273 613 329 614 51602 615 330 616 51932 617 331 618 52263 619 332 620 52595 621 333 622 52928 623 334 624 53262 625 335 626 53597 627 336 628 53933 629 337 630 54270 631 338 632 54608 633 339 634 54947 635 340 636 55287 637 341 638 55628 639 342 640 55970 641 343 642 56313 643 344 644 56657 645 345 646 57002 647 346 648 57348 649 347 650 57695 651 348 652 58043 653 349 654 58392 655 350 656 58742 657 351 658 59093 659 352 660 59445 661 353 662 59798 663 355 664 60153 665 356 666 60509 667 357 668 60866 669 358 670 61224 671 359 672 61583 673 360 674 61943 675 361 676 62304 677 362 678 62666 679 363 680 63029 681 364 682 63393 683 365 684 63758 685 366 686 64124 687 367 688 64491 689 368 690 64859 691 369 692 65228 693 370 694 65598 695 371 696 65969 697 372 698 66341 699 373 700 66714 701 374 702 67088 703 375 704 67463 705 376 706 67839 707 377 708 68216 709 378 710 68594 711 379 712 68973 713 380 714 69353 715 381 716 69734 717 382 718 70116 719 384 720 70500 721 385 722 70885 723 386 724 71271 725 387 726 71658 727 388 728 72046 729 389 730 72435 731 390 732 72825 733 391 734 73216 735 392 736 73608 737 393 738 74001 739 394 740 74395 741 395 742 74790 743 396 744 75186 745 397 746 75583 747 398 748 75981 749 399 750 76380 751 400 752 76780 753 401 754 77181 755 402 756 77583 757 403 758 77986 759 404 760 78390 761 405 762 78795 763 406 764 79201 765 407 766 79608 767 408 768 80016 769 409 770 80425 771 410 772 80835 773 411 774 81246 775 412 776 81658 777 413 778 82071 779 415 780 82486 781 416 782 82902 783 417 784 83319 785 418 786 83737 787 419 788 84156 789 420 790 84576 791 421 792 84997 793 422 794 85419 795 423 796 85842 797 424 798 86266 799 425 800 86691 801 426 802 87117 803 427 804 87544 805 428 806 87972 807 429 808 88401 809 430 810 88831 811 431 812 89262 813 432 814 89694 815 433 816 90127 817 434 818 90561 819 435 820 90996 821 436 822 91432 823 437 824 91869 825 438 826 92307 827 439 828 92746 829 440 830 93186 831 441 832 93627 833 442 834 94069 835 443 836 94512 837 444 838 94956 839 445 840 95401 841 447 842 95848 843 448 844 96296 845 449 846 96745 847 450 848 97195 849 451 850 97646 851 452 852 98098 853 453 854 98551 855 454 856 99005 857 455 858 99460 859 456 860 99916 861 457 862 100373 863 458 864 100831 865 459 866 101290 867 460 868 101750 869 461 870 102211 871 462 872 102673 873 463 874 103136 875 464 876 103600 877 465 878 104065 879 466 880 104531 881 467 882 104998 883 468 884 105466 885 469 886 105935 887 470 888 106405 889 471 890 106876 891 472 892 107348 893 473 894 107821 895 474 896 108295 897 475 898 108770 899 476 900 109246 901 477 902 109723 903 478 904 110201 905 480 906 110681 907 481 908 111162 909 482 910 111644 911 483 912 112127 913 484 914 112611 915 485 916 113096 917 486 918 113582 919 487 920 114069 921 488 922 114557 923 489 924 115046 925 490 926 115536 927 491 928 116027 929 492 930 116519 931 493 932 117012 933 494 934 117506 935 495 936 118001 937 496 938 118497 939 497 940 118994 941 498 942 119492 943 499 944 119991 945 500 946 120491 947 501 948 120992 949 502 950 121494 951 503 952 121997 953 504 954 122501 955 505 956 123006 957 506 958 123512 959 507 960 124019 961 508 962 124527 963 509 964 125036 965 510 966 125546 967 511 968 126057 969 512 970 126569 971 514 972 127083 973 515 974 127598 975 516 976 128114 977 517 978 128631 979 518 980 129149 981 519 982 129668 983 520 984 130188 985 521 986 130709 987 522 988 131231 989 523 990 131754 991 524 992 132278 993 525 994 132803 995 526 996 133329 997 527 998 133856 999 528 1000 134384 1001 529 1002 134913 1003 530 1004 135443 1005 531 1006 135974 1007 532 1008 136506 1009 533 1010 137039 1011 534 1012 137573 1013 535 1014 138108 1015 536 1016 138644 1017 537 1018 139181 1019 538 1020 139719 1021 539 1022 140258 1023 540 1024 140798 1025 541 1026 141339 1027 542 1028 141881 1029 543 1030 142424 1031 544 1032 142968 1033 545 1034 143513 1035 546 1036 144059 1037 547 1038 144606 1039 549 1040 145155 1041 550 1042 145705 1043 551 1044 146256 1045 552 1046 146808 1047 553 1048 147361 1049 554 1050 147915 1051 555 1052 148470 1053 556 1054 149026 1055 557 1056 149583 1057 558 1058 150141 1059 559 1060 150700 1061 560 1062 151260 1063 561 1064 151821 1065 562 1066 152383 1067 563 1068 152946 1069 564 1070 153510 1071 565 1072 154075 1073 566 1074 154641 1075 567 1076 155208 1077 568 1078 155776 1079 569 1080 156345 1081 570 1082 156915 1083 571 1084 157486 1085 572 1086 158058 1087 573 1088 158631 1089 574 1090 159205 1091 575 1092 159780 1093 576 1094 160356 1095 577 1096 160933 1097 578 1098 161511 1099 579 1100 162090 1101 580 1102 162670 1103 581 1104 163251 1105 582 1106 163833 1107 583 1108 164416 1109 585 1110 165001 1111 586 1112 165587 1113 587 1114 166174 1115 588 1116 166762 1117 589 1118 167351 1119 590 1120 167941 1121 591 1122 168532 1123 592 1124 169124 1125 593 1126 169717 1127 594 1128 170311 1129 595 1130 170906 1131 596 1132 171502 1133 597 1134 172099 1135 598 1136 172697 1137 599 1138 173296 1139 600 1140 173896 1141 601 1142 174497 1143 602 1144 175099 1145 603 1146 175702 1147 604 1148 176306 1149 605 1150 176911 1151 606 1152 177517 1153 607 1154 178124 1155 608 1156 178732 1157 609 1158 179341 1159 610 1160 179951 1161 611 1162 180562 1163 612 1164 181174 1165 613 1166 181787 1167 614 1168 182401 1169 615 1170 183016 1171 616 1172 183632 1173 617 1174 184249 1175 618 1176 184867 1177 619 1178 185486 1179 620 1180 186106 1181 622 1182 186728 1183 623 1184 187351 1185 624 1186 187975 1187 625 1188 188600 1189 626 1190 189226 1191 627 1192 189853 1193 628 1194 190481 1195 629 1196 191110 1197 630 1198 191740 1199 631 1200 192371 1201 632 1202 193003 1203 633 1204 193636 1205 634 1206 194270 1207 635 1208 194905 1209 636 1210 195541 1211 637 1212 196178 1213 638 1214 196816 1215 639 1216 197455 1217 640 1218 198095 1219 641 1220 198736 1221 642 1222 199378 1223 643 1224 200021 1225 644 1226 200665 1227 645 1228 201310 1229 646 1230 201956 1231 647 1232 202603 1233 648 1234 203251 1235 649 1236 203900 1237 650 1238 204550 1239 651 1240 205201 1241 652 1242 205853 1243 653 1244 206506 1245 654 1246 207160 1247 655 1248 207815 1249 656 1250 208471 1251 657 1252 209128 1253 658 1254 209786 1255 660 1256 210446 1257 661 1258 211107 1259 662 1260 211769 1261 663 1262 212432 1263 664 1264 213096 1265 665 1266 213761 1267 666 1268 214427 1269 667 1270 215094 1271 668 1272 215762 1273 669 1274 216431 1275 670 1276 217101 1277 671 1278 217772 1279 672 1280 218444 1281 673 1282 219117 1283 674 1284 219791 1285 675 1286 220466 1287 676 1288 221142 1289 677 1290 221819 1291 678 1292 222497 1293 679 1294 223176 1295 680 1296 223856 1297 681 1298 224537 1299 682 1300 225219 1301 683 1302 225902 1303 684 1304 226586 1305 685 1306 227271 1307 686 1308 227957 1309 687 1310 228644 1311 688 1312 229332 1313 689 1314 230021 1315 690 1316 230711 1317 691 1318 231402 1319 692 1320 232094 1321 693 1322 232787 1323 694 1324 233481 1325 695 1326 234176 1327 696 1328 234872 1329 697 1330 235569 1331 699 1332 236268 1333 700 1334 236968 1335 701 1336 237669 1337 702 1338 238371 1339 703 1340 239074 1341 704 1342 239778 1343 705 1344 240483 1345 706 1346 241189 1347 707 1348 241896 1349 708 1350 242604 1351 709 1352 243313 1353 710 1354 244023 1355 711 1356 244734 1357 712 1358 245446 1359 713 1360 246159 1361 714 1362 246873 1363 715 1364 247588 1365 716 1366 248304 1367 717 1368 249021 1369 718 1370 249739 1371 719 1372 250458 1373 720 1374 251178 1375 721 1376 251899 1377 722 1378 252621 1379 723 1380 253344 1381 724 1382 254068 1383 725 1384 254793 1385 726 1386 255519 1387 727 1388 256246 1389 728 1390 256974 1391 729 1392 257703 1393 730 1394 258433 1395 731 1396 259164 1397 732 1398 259896 1399 733 1400 260629 1401 734 1402 261363 1403 735 1404 262098 1405 736 1406 262834 1407 737 1408 263571 1409 738 1410 264309 1411 740 1412 265049 1413 741 1414 265790 1415 742 1416 266532 1417 743 1418 267275 1419 744 1420 268019 1421 745 1422 268764 1423 746 1424 269510 1425 747 1426 270257 1427 748 1428 271005 1429 749 1430 271754 1431 750 1432 272504 1433 751 1434 273255 1435 752 1436 274007 1437 753 1438 274760 1439 754 1440 275514 1441 755 1442 276269 1443 756 1444 277025 1445 757 1446 277782 1447 758 1448 278540 1449 759 1450 279299 1451 760 1452 280059 1453 761 1454 280820 1455 762 1456 281582 1457 763 1458 282345 1459 764 1460 283109 1461 765 1462 283874 1463 766 1464 284640 1465 767 1466 285407 1467 768 1468 286175 1469 769 1470 286944 1471 770 1472 287714 1473 771 1474 288485 1475 772 1476 289257 1477 773 1478 290030 1479 774 1480 290804 1481 775 1482 291579 1483 776 1484 292355 1485 777 1486 293132 1487 778 1488 293910 1489 779 1490 294689 1491 780 1492 295469 1493 782 1494 296251 1495 783 1496 297034 1497 784 1498 297818 1499 785 1500 298603 1501 786 1502 299389 1503 787 1504 300176 1505 788 1506 300964 1507 789 1508 301753 1509 790 1510 302543 1511 791 1512 303334 1513 792 1514 304126 1515 793 1516 304919 1517 794 1518 305713 1519 795 1520 306508 1521 796 1522 307304 1523 797 1524 308101 1525 798 1526 308899 1527 799 1528 309698 1529 800 1530 310498 1531 801 1532 311299 1533 802 1534 312101 1535 803 1536 312904 1537 804 1538 313708 1539 805 1540 314513 1541 806 1542 315319 1543 807 1544 316126 1545 808 1546 316934 1547 809 1548 317743 1549 810 1550 318553 1551 811 1552 319364 1553 812 1554 320176 1555 813 1556 320989 1557 814 1558 321803 1559 815 1560 322618 1561 816 1562 323434 1563 817 1564 324251 1565 818 1566 325069 1567 819 1568 325888 1569 820 1570 326708 1571 821 1572 327529 1573 822 1574 328351 1575 823 1576 329174 1577 825 1578 329999 1579 826 1580 330825 1581 827 1582 331652 1583 828 1584 332480 1585 829 1586 333309 1587 830 1588 334139 1589 831 1590 334970 1591 832 1592 335802 1593 833 1594 336635 1595 834 1596 337469 1597 835 1598 338304 1599 836 1600 339140 1601 837 1602 339977 1603 838 1604 340815 1605 839 1606 341654 1607 840 1608 342494 1609 841 1610 343335 1611 842 1612 344177 1613 843 1614 345020 1615 844 1616 345864 1617 845 1618 346709 1619 846 1620 347555 1621 847 1622 348402 1623 848 1624 349250 1625 849 1626 350099 1627 850 1628 350949 1629 851 1630 351800 1631 852 1632 352652 1633 853 1634 353505 1635 854 1636 354359 1637 855 1638 355214 1639 856 1640 356070 1641 857 1642 356927 1643 858 1644 357785 1645 859 1646 358644 1647 860 1648 359504 1649 861 1650 360365 1651 862 1652 361227 1653 863 1654 362090 1655 864 1656 362954 1657 865 1658 363819 1659 866 1660 364685 1661 867 1662 365552 1663 869 1664 366421 1665 870 1666 367291 1667 871 1668 368162 1669 872 1670 369034 1671 873 1672 369907 1673 874 1674 370781 1675 875 1676 371656 1677 876 1678 372532 1679 877 1680 373409 1681 878 1682 374287 1683 879 1684 375166 1685 880 1686 376046 1687 881 1688 376927 1689 882 1690 377809 1691 883 1692 378692 1693 884 1694 379576 1695 885 1696 380461 1697 886 1698 381347 1699 887 1700 382234 1701 888 1702 383122 1703 889 1704 384011 1705 890 1706 384901 1707 891 1708 385792 1709 892 1710 386684 1711 893 1712 387577 1713 894 1714 388471 1715 895 1716 389366 1717 896 1718 390262 1719 897 1720 391159 1721 898 1722 392057 1723 899 1724 392956 1725 900 1726 393856 1727 901 1728 394757 1729 902 1730 395659 1731 903 1732 396562 1733 904 1734 397466 1735 905 1736 398371 1737 906 1738 399277 1739 907 1740 400184 1741 908 1742 401092 1743 909 1744 402001 1745 910 1746 402911 1747 911 1748 403822 1749 912 1750 404734 1751 914 1752 405648 1753 915 1754 406563 1755 916 1756 407479 1757 917 1758 408396 1759 918 1760 409314 1761 919 1762 410233 1763 920 1764 411153 1765 921 1766 412074 1767 922 1768 412996 1769 923 1770 413919 1771 924 1772 414843 1773 925 1774 415768 1775 926 1776 416694 1777 927 1778 417621 1779 928 1780 418549 1781 929 1782 419478 1783 930 1784 420408 1785 931 1786 421339 1787 932 1788 422271 1789 933 1790 423204 1791 934 1792 424138 1793 935 1794 425073 1795 936 1796 426009 1797 937 1798 426946 1799 938 1800 427884 1801 939 1802 428823 1803 940 1804 429763 1805 941 1806 430704 1807 942 1808 431646 1809 943 1810 432589 1811 944 1812 433533 1813 945 1814 434478 1815 946 1816 435424 1817 947 1818 436371 1819 948 1820 437319 1821 949 1822 438268 1823 950 1824 439218 1825 951 1826 440169 1827 952 1828 441121 1829 953 1830 442074 1831 954 1832 443028 1833 955 1834 443983 1835 956 1836 444939 1837 957 1838 445896 1839 958 1840 446854 1841 960 1842 447814 1843 961 1844 448775 1845 962 1846 449737 1847 963 1848 450700 1849 964 1850 451664 1851 965 1852 452629 1853 966 1854 453595 1855 967 1856 454562 1857 968 1858 455530 1859 969 1860 456499 1861 970 1862 457469 1863 971 1864 458440 1865 972 1866 459412 1867 973 1868 460385 1869 974 1870 461359 1871 975 1872 462334 1873 976 1874 463310 1875 977 1876 464287 1877 978 1878 465265 1879 979 1880 466244 1881 980 1882 467224 1883 981 1884 468205 1885 982 1886 469187 1887 983 1888 470170 1889 984 1890 471154 1891 985 1892 472139 1893 986 1894 473125 1895 987 1896 474112 1897 988 1898 475100 1899 989 1900 476089 1901 990 1902 477079 1903 991 1904 478070 1905 992 1906 479062 1907 993 1908 480055 1909 994 1910 481049 1911 995 1912 482044 1913 996 1914 483040 1915 997 1916 484037 1917 998 1918 485035 1919 999 1920 486034 1921 1000 1922 487034 1923 1001 1924 488035 1925 1002 1926 489037 1927 1003 1928 490040 1929 1004 1930 491044 1931 1005 1932 492049 1933 1007 1934 493056 1935 1008 1936 494064 1937 1009 1938 495073 1939 1010 1940 496083 1941 1011 1942 497094 1943 1012 1944 498106 1945 1013 1946 499119 1947 1014 1948 500133 1949 1015 1950 501148 1951 1016 1952 502164 1953 1017 1954 503181 1955 1018 1956 504199 1957 1019 1958 505218 1959 1020 1960 506238 1961 1021 1962 507259 1963 1022 1964 508281 1965 1023 1966 509304 1967 1024 1968 510328 1969 1025 1970 511353 1971 1026 1972 512379 1973 1027 1974 513406 1975 1028 1976 514434 1977 1029 1978 515463 1979 1030 1980 516493 1981 1031 1982 517524 1983 1032 1984 518556 1985 1033 1986 519589 1987 1034 1988 520623 1989 1035 1990 521658 1991 1036 1992 522694 1993 1037 1994 523731 1995 1038 1996 524769 1997 1039 1998 525808 1999 1040 2000 526848 2001 1041