0 0 1 1 2 2 3 3 4 4 5 7 6 5 7 12 8 6 9 18 10 8 11 26 12 9 13 35 14 10 15 45 16 11 17 56 18 13 19 69 20 14 21 83 22 15 23 98 24 16 25 114 26 17 27 131 28 19 29 150 30 20 31 170 32 21 33 191 34 22 35 213 36 23 37 236 38 24 39 260 40 25 41 285 42 27 43 312 44 28 45 340 46 29 47 369 48 30 49 399 50 31 51 430 52 32 53 462 54 33 55 495 56 34 57 529 58 36 59 565 60 37 61 602 62 38 63 640 64 39 65 679 66 40 67 719 68 41 69 760 70 42 71 802 72 43 73 845 74 44 75 889 76 46 77 935 78 47 79 982 80 48 81 1030 82 49 83 1079 84 50 85 1129 86 51 87 1180 88 52 89 1232 90 53 91 1285 92 54 93 1339 94 55 95 1394 96 57 97 1451 98 58 99 1509 100 59 101 1568 102 60 103 1628 104 61 105 1689 106 62 107 1751 108 63 109 1814 110 64 111 1878 112 65 113 1943 114 66 115 2009 116 67 117 2076 118 68 119 2144 120 70 121 2214 122 71 123 2285 124 72 125 2357 126 73 127 2430 128 74 129 2504 130 75 131 2579 132 76 133 2655 134 77 135 2732 136 78 137 2810 138 79 139 2889 140 80 141 2969 142 81 143 3050 144 82 145 3132 146 84 147 3216 148 85 149 3301 150 86 151 3387 152 87 153 3474 154 88 155 3562 156 89 157 3651 158 90 159 3741 160 91 161 3832 162 92 163 3924 164 93 165 4017 166 94 167 4111 168 95 169 4206 170 96 171 4302 172 97 173 4399 174 99 175 4498 176 100 177 4598 178 101 179 4699 180 102 181 4801 182 103 183 4904 184 104 185 5008 186 105 187 5113 188 106 189 5219 190 107 191 5326 192 108 193 5434 194 109 195 5543 196 110 197 5653 198 111 199 5764 200 112 201 5876 202 113 203 5989 204 115 205 6104 206 116 207 6220 208 117 209 6337 210 118 211 6455 212 119 213 6574 214 120 215 6694 216 121 217 6815 218 122 219 6937 220 123 221 7060 222 124 223 7184 224 125 225 7309 226 126 227 7435 228 127 229 7562 230 128 231 7690 232 129 233 7819 234 130 235 7949 236 132 237 8081 238 133 239 8214 240 134 241 8348 242 135 243 8483 244 136 245 8619 246 137 247 8756 248 138 249 8894 250 139 251 9033 252 140 253 9173 254 141 255 9314 256 142 257 9456 258 143 259 9599 260 144 261 9743 262 145 263 9888 264 146 265 10034 266 147 267 10181 268 148 269 10329 270 149 271 10478 272 151 273 10629 274 152 275 10781 276 153 277 10934 278 154 279 11088 280 155 281 11243 282 156 283 11399 284 157 285 11556 286 158 287 11714 288 159 289 11873 290 160 291 12033 292 161 293 12194 294 162 295 12356 296 163 297 12519 298 164 299 12683 300 165 301 12848 302 166 303 13014 304 167 305 13181 306 168 307 13349 308 169 309 13518 310 171 311 13689 312 172 313 13861 314 173 315 14034 316 174 317 14208 318 175 319 14383 320 176 321 14559 322 177 323 14736 324 178 325 14914 326 179 327 15093 328 180 329 15273 330 181 331 15454 332 182 333 15636 334 183 335 15819 336 184 337 16003 338 185 339 16188 340 186 341 16374 342 187 343 16561 344 188 345 16749 346 189 347 16938 348 190 349 17128 350 192 351 17320 352 193 353 17513 354 194 355 17707 356 195 357 17902 358 196 359 18098 360 197 361 18295 362 198 363 18493 364 199 365 18692 366 200 367 18892 368 201 369 19093 370 202 371 19295 372 203 373 19498 374 204 375 19702 376 205 377 19907 378 206 379 20113 380 207 381 20320 382 208 383 20528 384 209 385 20737 386 210 387 20947 388 211 389 21158 390 212 391 21370 392 214 393 21584 394 215 395 21799 396 216 397 22015 398 217 399 22232 400 218 401 22450 402 219 403 22669 404 220 405 22889 406 221 407 23110 408 222 409 23332 410 223 411 23555 412 224 413 23779 414 225 415 24004 416 226 417 24230 418 227 419 24457 420 228 421 24685 422 229 423 24914 424 230 425 25144 426 231 427 25375 428 232 429 25607 430 233 431 25840 432 234 433 26074 434 235 435 26309 436 237 437 26546 438 238 439 26784 440 239 441 27023 442 240 443 27263 444 241 445 27504 446 242 447 27746 448 243 449 27989 450 244 451 28233 452 245 453 28478 454 246 455 28724 456 247 457 28971 458 248 459 29219 460 249 461 29468 462 250 463 29718 464 251 465 29969 466 252 467 30221 468 253 469 30474 470 254 471 30728 472 255 473 30983 474 256 475 31239 476 257 477 31496 478 258 479 31754 480 259 481 32013 482 261 483 32274 484 262 485 32536 486 263 487 32799 488 264 489 33063 490 265 491 33328 492 266 493 33594 494 267 495 33861 496 268 497 34129 498 269 499 34398 500 270 501 34668 502 271 503 34939 504 272 505 35211 506 273 507 35484 508 274 509 35758 510 275 511 36033 512 276 513 36309 514 277 515 36586 516 278 517 36864 518 279 519 37143 520 280 521 37423 522 281 523 37704 524 282 525 37986 526 283 527 38269 528 284 529 38553 530 286 531 38839 532 287 533 39126 534 288 535 39414 536 289 537 39703 538 290 539 39993 540 291 541 40284 542 292 543 40576 544 293 545 40869 546 294 547 41163 548 295 549 41458 550 296 551 41754 552 297 553 42051 554 298 555 42349 556 299 557 42648 558 300 559 42948 560 301 561 43249 562 302 563 43551 564 303 565 43854 566 304 567 44158 568 305 569 44463 570 306 571 44769 572 307 573 45076 574 308 575 45384 576 309 577 45693 578 310 579 46003 580 311 581 46314 582 313 583 46627 584 314 585 46941 586 315 587 47256 588 316 589 47572 590 317 591 47889 592 318 593 48207 594 319 595 48526 596 320 597 48846 598 321 599 49167 600 322 601 49489 602 323 603 49812 604 324 605 50136 606 325 607 50461 608 326 609 50787 610 327 611 51114 612 328 613 51442 614 329 615 51771 616 330 617 52101 618 331 619 52432 620 332 621 52764 622 333 623 53097 624 334 625 53431 626 335 627 53766 628 336 629 54102 630 337 631 54439 632 338 633 54777 634 339 635 55116 636 341 637 55457 638 342 639 55799 640 343 641 56142 642 344 643 56486 644 345 645 56831 646 346 647 57177 648 347 649 57524 650 348 651 57872 652 349 653 58221 654 350 655 58571 656 351 657 58922 658 352 659 59274 660 353 661 59627 662 354 663 59981 664 355 665 60336 666 356 667 60692 668 357 669 61049 670 358 671 61407 672 359 673 61766 674 360 675 62126 676 361 677 62487 678 362 679 62849 680 363 681 63212 682 364 683 63576 684 365 685 63941 686 366 687 64307 688 367 689 64674 690 368 691 65042 692 370 693 65412 694 371 695 65783 696 372 697 66155 698 373 699 66528 700 374 701 66902 702 375 703 67277 704 376 705 67653 706 377 707 68030 708 378 709 68408 710 379 711 68787 712 380 713 69167 714 381 715 69548 716 382 717 69930 718 383 719 70313 720 384 721 70697 722 385 723 71082 724 386 725 71468 726 387 727 71855 728 388 729 72243 730 389 731 72632 732 390 733 73022 734 391 735 73413 736 392 737 73805 738 393 739 74198 740 394 741 74592 742 395 743 74987 744 396 745 75383 746 397 747 75780 748 398 749 76178 750 400 751 76578 752 401 753 76979 754 402 755 77381 756 403 757 77784 758 404 759 78188 760 405 761 78593 762 406 763 78999 764 407 765 79406 766 408 767 79814 768 409 769 80223 770 410 771 80633 772 411 773 81044 774 412 775 81456 776 413 777 81869 778 414 779 82283 780 415 781 82698 782 416 783 83114 784 417 785 83531 786 418 787 83949 788 419 789 84368 790 420 791 84788 792 421 793 85209 794 422 795 85631 796 423 797 86054 798 424 799 86478 800 425 801 86903 802 426 803 87329 804 427 805 87756 806 428 807 88184 808 429 809 88613 810 431 811 89044 812 432 813 89476 814 433 815 89909 816 434 817 90343 818 435 819 90778 820 436 821 91214 822 437 823 91651 824 438 825 92089 826 439 827 92528 828 440 829 92968 830 441 831 93409 832 442 833 93851 834 443 835 94294 836 444 837 94738 838 445 839 95183 840 446 841 95629 842 447 843 96076 844 448 845 96524 846 449 847 96973 848 450 849 97423 850 451 851 97874 852 452 853 98326 854 453 855 98779 856 454 857 99233 858 455 859 99688 860 456 861 100144 862 457 863 100601 864 458 865 101059 866 459 867 101518 868 460 869 101978 870 461 871 102439 872 463 873 102902 874 464 875 103366 876 465 877 103831 878 466 879 104297 880 467 881 104764 882 468 883 105232 884 469 885 105701 886 470 887 106171 888 471 889 106642 890 472 891 107114 892 473 893 107587 894 474 895 108061 896 475 897 108536 898 476 899 109012 900 477 901 109489 902 478 903 109967 904 479 905 110446 906 480 907 110926 908 481 909 111407 910 482 911 111889 912 483 913 112372 914 484 915 112856 916 485 917 113341 918 486 919 113827 920 487 921 114314 922 488 923 114802 924 489 925 115291 926 490 927 115781 928 491 929 116272 930 492 931 116764 932 493 933 117257 934 494 935 117751 936 496 937 118247 938 497 939 118744 940 498 941 119242 942 499 943 119741 944 500 945 120241 946 501 947 120742 948 502 949 121244 950 503 951 121747 952 504 953 122251 954 505 955 122756 956 506 957 123262 958 507 959 123769 960 508 961 124277 962 509 963 124786 964 510 965 125296 966 511 967 125807 968 512 969 126319 970 513 971 126832 972 514 973 127346 974 515 975 127861 976 516 977 128377 978 517 979 128894 980 518 981 129412 982 519 983 129931 984 520 985 130451 986 521 987 130972 988 522 989 131494 990 523 991 132017 992 524 993 132541 994 525 995 133066 996 526 997 133592 998 527 999 134119 1000 528 1001 134647 1002 530 1003 135177 1004 531 1005 135708 1006 532 1007 136240 1008 533 1009 136773 1010 534 1011 137307 1012 535 1013 137842 1014 536 1015 138378 1016 537 1017 138915 1018 538 1019 139453 1020 539 1021 139992 1022 540 1023 140532 1024 541 1025 141073 1026 542 1027 141615 1028 543 1029 142158 1030 544 1031 142702 1032 545 1033 143247 1034 546 1035 143793 1036 547 1037 144340 1038 548 1039 144888 1040 549 1041 145437 1042 550 1043 145987 1044 551 1045 146538 1046 552 1047 147090 1048 553 1049 147643 1050 554 1051 148197 1052 555 1053 148752 1054 556 1055 149308 1056 557 1057 149865 1058 558 1059 150423 1060 559 1061 150982 1062 560 1063 151542 1064 561 1065 152103 1066 562 1067 152665 1068 563 1069 153228 1070 564 1071 153792 1072 566 1073 154358 1074 567 1075 154925 1076 568 1077 155493 1078 569 1079 156062 1080 570 1081 156632 1082 571 1083 157203 1084 572 1085 157775 1086 573 1087 158348 1088 574 1089 158922 1090 575 1091 159497 1092 576 1093 160073 1094 577 1095 160650 1096 578 1097 161228 1098 579 1099 161807 1100 580 1101 162387 1102 581 1103 162968 1104 582 1105 163550 1106 583 1107 164133 1108 584 1109 164717 1110 585 1111 165302 1112 586 1113 165888 1114 587 1115 166475 1116 588 1117 167063 1118 589 1119 167652 1120 590 1121 168242 1122 591 1123 168833 1124 592 1125 169425 1126 593 1127 170018 1128 594 1129 170612 1130 595 1131 171207 1132 596 1133 171803 1134 597 1135 172400 1136 598 1137 172998 1138 599 1139 173597 1140 600 1141 174197 1142 601 1143 174798 1144 603 1145 175401 1146 604 1147 176005 1148 605 1149 176610 1150 606 1151 177216 1152 607 1153 177823 1154 608 1155 178431 1156 609 1157 179040 1158 610 1159 179650 1160 611 1161 180261 1162 612 1163 180873 1164 613 1165 181486 1166 614 1167 182100 1168 615 1169 182715 1170 616 1171 183331 1172 617 1173 183948 1174 618 1175 184566 1176 619 1177 185185 1178 620 1179 185805 1180 621 1181 186426 1182 622 1183 187048 1184 623 1185 187671 1186 624 1187 188295 1188 625 1189 188920 1190 626 1191 189546 1192 627 1193 190173 1194 628 1195 190801 1196 629 1197 191430 1198 630 1199 192060 1200 631 1201 192691 1202 632 1203 193323 1204 633 1205 193956 1206 634 1207 194590 1208 635 1209 195225 1210 636 1211 195861 1212 637 1213 196498 1214 638 1215 197136 1216 639 1217 197775 1218 641 1219 198416 1220 642 1221 199058 1222 643 1223 199701 1224 644 1225 200345 1226 645 1227 200990 1228 646 1229 201636 1230 647 1231 202283 1232 648 1233 202931 1234 649 1235 203580 1236 650 1237 204230 1238 651 1239 204881 1240 652 1241 205533 1242 653 1243 206186 1244 654 1245 206840 1246 655 1247 207495 1248 656 1249 208151 1250 657 1251 208808 1252 658 1253 209466 1254 659 1255 210125 1256 660 1257 210785 1258 661 1259 211446 1260 662 1261 212108 1262 663 1263 212771 1264 664 1265 213435 1266 665 1267 214100 1268 666 1269 214766 1270 667 1271 215433 1272 668 1273 216101 1274 669 1275 216770 1276 670 1277 217440 1278 671 1279 218111 1280 672 1281 218783 1282 673 1283 219456 1284 674 1285 220130 1286 675 1287 220805 1288 676 1289 221481 1290 677 1291 222158 1292 678 1293 222836 1294 680 1295 223516 1296 681 1297 224197 1298 682 1299 224879 1300 683 1301 225562 1302 684 1303 226246 1304 685 1305 226931 1306 686 1307 227617 1308 687 1309 228304 1310 688 1311 228992 1312 689 1313 229681 1314 690 1315 230371 1316 691 1317 231062 1318 692 1319 231754 1320 693 1321 232447 1322 694 1323 233141 1324 695 1325 233836 1326 696 1327 234532 1328 697 1329 235229 1330 698 1331 235927 1332 699 1333 236626 1334 700 1335 237326 1336 701 1337 238027 1338 702 1339 238729 1340 703 1341 239432 1342 704 1343 240136 1344 705 1345 240841 1346 706 1347 241547 1348 707 1349 242254 1350 708 1351 242962 1352 709 1353 243671 1354 710 1355 244381 1356 711 1357 245092 1358 712 1359 245804 1360 713 1361 246517 1362 714 1363 247231 1364 715 1365 247946 1366 716 1367 248662 1368 717 1369 249379 1370 718 1371 250097 1372 720 1373 250817 1374 721 1375 251538 1376 722 1377 252260 1378 723 1379 252983 1380 724 1381 253707 1382 725 1383 254432 1384 726 1385 255158 1386 727 1387 255885 1388 728 1389 256613 1390 729 1391 257342 1392 730 1393 258072 1394 731 1395 258803 1396 732 1397 259535 1398 733 1399 260268 1400 734 1401 261002 1402 735 1403 261737 1404 736 1405 262473 1406 737 1407 263210 1408 738 1409 263948 1410 739 1411 264687 1412 740 1413 265427 1414 741 1415 266168 1416 742 1417 266910 1418 743 1419 267653 1420 744 1421 268397 1422 745 1423 269142 1424 746 1425 269888 1426 747 1427 270635 1428 748 1429 271383 1430 749 1431 272132 1432 750 1433 272882 1434 751 1435 273633 1436 752 1437 274385 1438 753 1439 275138 1440 754 1441 275892 1442 755 1443 276647 1444 756 1445 277403 1446 757 1447 278160 1448 758 1449 278918 1450 759 1451 279677 1452 761 1453 280438 1454 762 1455 281200 1456 763 1457 281963 1458 764 1459 282727 1460 765 1461 283492 1462 766 1463 284258 1464 767 1465 285025 1466 768 1467 285793 1468 769 1469 286562 1470 770 1471 287332 1472 771 1473 288103 1474 772 1475 288875 1476 773 1477 289648 1478 774 1479 290422 1480 775 1481 291197 1482 776 1483 291973 1484 777 1485 292750 1486 778 1487 293528 1488 779 1489 294307 1490 780 1491 295087 1492 781 1493 295868 1494 782 1495 296650 1496 783 1497 297433 1498 784 1499 298217 1500 785 1501 299002 1502 786 1503 299788 1504 787 1505 300575 1506 788 1507 301363 1508 789 1509 302152 1510 790 1511 302942 1512 791 1513 303733 1514 792 1515 304525 1516 793 1517 305318 1518 794 1519 306112 1520 795 1521 306907 1522 796 1523 307703 1524 797 1525 308500 1526 798 1527 309298 1528 799 1529 310097 1530 800 1531 310897 1532 801 1533 311698 1534 803 1535 312501 1536 804 1537 313305 1538 805 1539 314110 1540 806 1541 314916 1542 807 1543 315723 1544 808 1545 316531 1546 809 1547 317340 1548 810 1549 318150 1550 811 1551 318961 1552 812 1553 319773 1554 813 1555 320586 1556 814 1557 321400 1558 815 1559 322215 1560 816 1561 323031 1562 817 1563 323848 1564 818 1565 324666 1566 819 1567 325485 1568 820 1569 326305 1570 821 1571 327126 1572 822 1573 327948 1574 823 1575 328771 1576 824 1577 329595 1578 825 1579 330420 1580 826 1581 331246 1582 827 1583 332073 1584 828 1585 332901 1586 829 1587 333730 1588 830 1589 334560 1590 831 1591 335391 1592 832 1593 336223 1594 833 1595 337056 1596 834 1597 337890 1598 835 1599 338725 1600 836 1601 339561 1602 837 1603 340398 1604 838 1605 341236 1606 839 1607 342075 1608 840 1609 342915 1610 841 1611 343756 1612 842 1613 344598 1614 843 1615 345441 1616 844 1617 346285 1618 846 1619 347131 1620 847 1621 347978 1622 848 1623 348826 1624 849 1625 349675 1626 850 1627 350525 1628 851 1629 351376 1630 852 1631 352228 1632 853 1633 353081 1634 854 1635 353935 1636 855 1637 354790 1638 856 1639 355646 1640 857 1641 356503 1642 858 1643 357361 1644 859 1645 358220 1646 860 1647 359080 1648 861 1649 359941 1650 862 1651 360803 1652 863 1653 361666 1654 864 1655 362530 1656 865 1657 363395 1658 866 1659 364261 1660 867 1661 365128 1662 868 1663 365996 1664 869 1665 366865 1666 870 1667 367735 1668 871 1669 368606 1670 872 1671 369478 1672 873 1673 370351 1674 874 1675 371225 1676 875 1677 372100 1678 876 1679 372976 1680 877 1681 373853 1682 878 1683 374731 1684 879 1685 375610 1686 880 1687 376490 1688 881 1689 377371 1690 882 1691 378253 1692 883 1693 379136 1694 884 1695 380020 1696 885 1697 380905 1698 886 1699 381791 1700 887 1701 382678 1702 888 1703 383566 1704 890 1705 384456 1706 891 1707 385347 1708 892 1709 386239 1710 893 1711 387132 1712 894 1713 388026 1714 895 1715 388921 1716 896 1717 389817 1718 897 1719 390714 1720 898 1721 391612 1722 899 1723 392511 1724 900 1725 393411 1726 901 1727 394312 1728 902 1729 395214 1730 903 1731 396117 1732 904 1733 397021 1734 905 1735 397926 1736 906 1737 398832 1738 907 1739 399739 1740 908 1741 400647 1742 909 1743 401556 1744 910 1745 402466 1746 911 1747 403377 1748 912 1749 404289 1750 913 1751 405202 1752 914 1753 406116 1754 915 1755 407031 1756 916 1757 407947 1758 917 1759 408864 1760 918 1761 409782 1762 919 1763 410701 1764 920 1765 411621 1766 921 1767 412542 1768 922 1769 413464 1770 923 1771 414387 1772 924 1773 415311 1774 925 1775 416236 1776 926 1777 417162 1778 927 1779 418089 1780 928 1781 419017 1782 929 1783 419946 1784 930 1785 420876 1786 931 1787 421807 1788 932 1789 422739 1790 933 1791 423672 1792 934 1793 424606 1794 936 1795 425542 1796 937 1797 426479 1798 938 1799 427417 1800 939 1801 428356 1802 940 1803 429296 1804 941 1805 430237 1806 942 1807 431179 1808 943 1809 432122 1810 944 1811 433066 1812 945 1813 434011 1814 946 1815 434957 1816 947 1817 435904 1818 948 1819 436852 1820 949 1821 437801 1822 950 1823 438751 1824 951 1825 439702 1826 952 1827 440654 1828 953 1829 441607 1830 954 1831 442561 1832 955 1833 443516 1834 956 1835 444472 1836 957 1837 445429 1838 958 1839 446387 1840 959 1841 447346 1842 960 1843 448306 1844 961 1845 449267 1846 962 1847 450229 1848 963 1849 451192 1850 964 1851 452156 1852 965 1853 453121 1854 966 1855 454087 1856 967 1857 455054 1858 968 1859 456022 1860 969 1861 456991 1862 970 1863 457961 1864 971 1865 458932 1866 972 1867 459904 1868 973 1869 460877 1870 974 1871 461851 1872 975 1873 462826 1874 976 1875 463802 1876 977 1877 464779 1878 978 1879 465757 1880 979 1881 466736 1882 980 1883 467716 1884 981 1885 468697 1886 983 1887 469680 1888 984 1889 470664 1890 985 1891 471649 1892 986 1893 472635 1894 987 1895 473622 1896 988 1897 474610 1898 989 1899 475599 1900 990 1901 476589 1902 991 1903 477580 1904 992 1905 478572 1906 993 1907 479565 1908 994 1909 480559 1910 995 1911 481554 1912 996 1913 482550 1914 997 1915 483547 1916 998 1917 484545 1918 999 1919 485544 1920 1000 1921 486544 1922 1001 1923 487545 1924 1002 1925 488547 1926 1003 1927 489550 1928 1004 1929 490554 1930 1005 1931 491559 1932 1006 1933 492565 1934 1007 1935 493572 1936 1008 1937 494580 1938 1009 1939 495589 1940 1010 1941 496599 1942 1011 1943 497610 1944 1012 1945 498622 1946 1013 1947 499635 1948 1014 1949 500649 1950 1015 1951 501664 1952 1016 1953 502680 1954 1017 1955 503697 1956 1018 1957 504715 1958 1019 1959 505734 1960 1020 1961 506754 1962 1021 1963 507775 1964 1022 1965 508797 1966 1023 1967 509820 1968 1024 1969 510844 1970 1025 1971 511869 1972 1026 1973 512895 1974 1027 1975 513922 1976 1028 1977 514950 1978 1029 1979 515979 1980 1031 1981 517010 1982 1032 1983 518042 1984 1033 1985 519075 1986 1034 1987 520109 1988 1035 1989 521144 1990 1036 1991 522180 1992 1037 1993 523217 1994 1038 1995 524255 1996 1039 1997 525294 1998 1040 1999 526334 2000 1041