0 1 1 4 2 10 3 11 4 13 5 14 6 16 7 23 8 25 9 34 10 35 11 37 12 38 13 40 14 44 15 47 16 49 17 52 18 56 19 58 20 59 21 61 22 62 23 64 24 71 25 73 26 82 27 83 28 85 29 86 30 92 31 95 32 97 33 100 34 106 35 107 36 109 37 110 38 119 39 121 40 130 41 131 42 133 43 134 44 136 45 140 46 143 47 145 48 148 49 152 50 154 51 155 52 157 53 158 54 160 55 167 56 169 57 176 58 178 59 179 60 181 61 182 62 188 63 191 64 193 65 196 66 202 67 203 68 205 69 206 70 208 71 215 72 217 73 224 74 226 75 227 76 229 77 230 78 232 79 236 80 239 81 241 82 244 83 248 84 250 85 251 86 253 87 254 88 256 89 263 90 265 91 274 92 275 93 277 94 278 95 284 96 287 97 289 98 292 99 298 100 299 101 301 102 302 103 311 104 313 105 322 106 323 107 325 108 326 109 328 110 332 111 335 112 337 113 340 114 344 115 346 116 347 117 349 118 350 119 359 120 361 121 368 122 370 123 371 124 373 125 374 126 380 127 383 128 385 129 388 130 394 131 395 132 397 133 398 134 400 135 407 136 409 137 418 138 419 139 421 140 422 141 424 142 428 143 431 144 433 145 436 146 440 147 442 148 443 149 445 150 446 151 455 152 457 153 466 154 467 155 469 156 470 157 476 158 479 159 481 160 484 161 490 162 491 163 493 164 494 165 503 166 505 167 514 168 515 169 517 170 518 171 520 172 524 173 527 174 529 175 532 176 536 177 538 178 539 179 541 180 542 181 544 182 551 183 553 184 560 185 562 186 563 187 565 188 566 189 572 190 575 191 577 192 580 193 586 194 587 195 589 196 590 197 592 198 599 199 601 200 608 201 610 202 611 203 613 204 614 205 616 206 620 207 623 208 625 209 628 210 632 211 634 212 635 213 637 214 638 215 640 216 647 217 649 218 658 219 659 220 661 221 662 222 668 223 671 224 673 225 676 226 682 227 683 228 685 229 686 230 695 231 697 232 704 233 706 234 707 235 709 236 710 237 712 238 716 239 719 240 721 241 724 242 728 243 730 244 731 245 733 246 734 247 743 248 745 249 752 250 754 251 755 252 757 253 758 254 764 255 767 256 769 257 772 258 778 259 779 260 781 261 782 262 784 263 791 264 793 265 802 266 803 267 805 268 806 269 808 270 812 271 815 272 817 273 820 274 824 275 826 276 827 277 829 278 830 279 832 280 839 281 841 282 850 283 851 284 853 285 854 286 860 287 863 288 865 289 868 290 874 291 875 292 877 293 878 294 887 295 889 296 896 297 898 298 899 299 901 300 902 301 904 302 908 303 911 304 913 305 916 306 920 307 922 308 923 309 925 310 926 311 928 312 935 313 937 314 944 315 946 316 947 317 949 318 950 319 956 320 959 321 961 322 964 323 970 324 971 325 973 326 974 327 976 328 983 329 985 330 992 331 994 332 995 333 997 334 998 335 1000 336 1004 337 1007 338 1009 339 1012 340 1016 341 1018 342 1019 343 1021 344 1022 345 1024 346 1031 347 1033 348 1042 349 1043 350 1045 351 1046 352 1052 353 1055 354 1057 355 1060 356 1066 357 1067 358 1069 359 1070 360 1079 361 1081 362 1090 363 1091 364 1093 365 1094 366 1096 367 1100 368 1103 369 1105 370 1108 371 1112 372 1114 373 1115 374 1117 375 1118 376 1127 377 1129 378 1136 379 1138 380 1139 381 1141 382 1142 383 1148 384 1151 385 1153 386 1156 387 1162 388 1163 389 1165 390 1166 391 1168 392 1175 393 1177 394 1186 395 1187 396 1189 397 1190 398 1192 399 1196 400 1199 401 1201 402 1204 403 1208 404 1210 405 1211 406 1213 407 1214 408 1223 409 1225 410 1234 411 1235 412 1237 413 1238 414 1244 415 1247 416 1249 417 1252 418 1258 419 1259 420 1261 421 1262 422 1271 423 1273 424 1282 425 1283 426 1285 427 1286 428 1288 429 1292 430 1295 431 1297 432 1300 433 1304 434 1306 435 1307 436 1309 437 1310 438 1312 439 1319 440 1321 441 1328 442 1330 443 1331 444 1333 445 1334 446 1340 447 1343 448 1345 449 1348 450 1354 451 1355 452 1357 453 1358 454 1360 455 1367 456 1369 457 1376 458 1378 459 1379 460 1381 461 1382 462 1384 463 1388 464 1391 465 1393 466 1396 467 1400 468 1402 469 1403 470 1405 471 1406 472 1415 473 1417 474 1426 475 1427 476 1429 477 1430 478 1436 479 1439 480 1441 481 1444 482 1450 483 1451 484 1453 485 1454 486 1463 487 1465 488 1472 489 1474 490 1475 491 1477 492 1478 493 1480 494 1484 495 1487 496 1489 497 1492 498 1496 499 1498 500 1499 501 1501 502 1502 503 1511 504 1513 505 1520 506 1522 507 1523 508 1525 509 1526 510 1532 511 1535 512 1537 513 1540 514 1546 515 1547 516 1549 517 1550 518 1552 519 1559 520 1561 521 1570 522 1571 523 1573 524 1574 525 1576 526 1580 527 1583 528 1585 529 1588 530 1592 531 1594 532 1595 533 1597 534 1598 535 1600 536 1607 537 1609 538 1618 539 1619 540 1621 541 1622 542 1628 543 1631 544 1633 545 1636 546 1642 547 1643 548 1645 549 1646 550 1655 551 1657 552 1666 553 1667 554 1669 555 1670 556 1672 557 1676 558 1679 559 1681 560 1684 561 1688 562 1690 563 1691 564 1693 565 1694 566 1696 567 1703 568 1705 569 1712 570 1714 571 1715 572 1717 573 1718 574 1724 575 1727 576 1729 577 1732 578 1738 579 1739 580 1741 581 1742 582 1744 583 1751 584 1753 585 1760 586 1762 587 1763 588 1765 589 1766 590 1768 591 1772 592 1775 593 1777 594 1780 595 1784 596 1786 597 1787 598 1789 599 1790 600 1799 601 1801 602 1810 603 1811 604 1813 605 1814 606 1820 607 1823 608 1825 609 1828 610 1834 611 1835 612 1837 613 1838 614 1847 615 1849 616 1858 617 1859 618 1861 619 1862 620 1864 621 1868 622 1871 623 1873 624 1876 625 1880 626 1882 627 1883 628 1885 629 1886 630 1895 631 1897 632 1904 633 1906 634 1907 635 1909 636 1910 637 1916 638 1919 639 1921 640 1924 641 1930 642 1931 643 1933 644 1934 645 1936 646 1943 647 1945 648 1954 649 1955 650 1957 651 1958 652 1960 653 1964 654 1967 655 1969 656 1972 657 1976 658 1978 659 1979 660 1981 661 1982 662 1991 663 1993 664 2002 665 2003 666 2005 667 2006 668 2012 669 2015 670 2017 671 2020 672 2026 673 2027 674 2029 675 2030 676 2039 677 2041 678 2050 679 2051 680 2053 681 2054 682 2056 683 2060 684 2063 685 2065 686 2068 687 2072 688 2074 689 2075 690 2077 691 2078 692 2080 693 2087 694 2089 695 2096 696 2098 697 2099 698 2101 699 2102 700 2108 701 2111 702 2113 703 2116 704 2122 705 2123 706 2125 707 2126 708 2128 709 2135 710 2137 711 2144 712 2146 713 2147 714 2149 715 2150 716 2152 717 2156 718 2159 719 2161 720 2164 721 2168 722 2170 723 2171 724 2173 725 2174 726 2176 727 2183 728 2185 729 2194 730 2195 731 2197 732 2198 733 2204 734 2207 735 2209 736 2212 737 2218 738 2219 739 2221 740 2222 741 2231 742 2233 743 2240 744 2242 745 2243 746 2245 747 2246 748 2248 749 2252 750 2255 751 2257 752 2260 753 2264 754 2266 755 2267 756 2269 757 2270 758 2279 759 2281 760 2288 761 2290 762 2291 763 2293 764 2294 765 2300 766 2303 767 2305 768 2308 769 2314 770 2315 771 2317 772 2318 773 2320 774 2327 775 2329 776 2338 777 2339 778 2341 779 2342 780 2344 781 2348 782 2351 783 2353 784 2356 785 2360 786 2362 787 2363 788 2365 789 2366 790 2368 791 2375 792 2377 793 2386 794 2387 795 2389 796 2390 797 2396 798 2399 799 2401 800 2404 801 2410 802 2411 803 2413 804 2414 805 2423 806 2425 807 2432 808 2434 809 2435 810 2437 811 2438 812 2440 813 2444 814 2447 815 2449 816 2452 817 2456 818 2458 819 2459 820 2461 821 2462 822 2464 823 2471 824 2473 825 2480 826 2482 827 2483 828 2485 829 2486 830 2492 831 2495 832 2497 833 2500 834 2506 835 2507 836 2509 837 2510 838 2512 839 2519 840 2521 841 2528 842 2530 843 2531 844 2533 845 2534 846 2536 847 2540 848 2543 849 2545 850 2548 851 2552 852 2554 853 2555 854 2557 855 2558 856 2560 857 2567 858 2569 859 2578 860 2579 861 2581 862 2582 863 2588 864 2591 865 2593 866 2596 867 2602 868 2603 869 2605 870 2606 871 2615 872 2617 873 2626 874 2627 875 2629 876 2630 877 2632 878 2636 879 2639 880 2641 881 2644 882 2648 883 2650 884 2651 885 2653 886 2654 887 2663 888 2665 889 2672 890 2674 891 2675 892 2677 893 2678 894 2684 895 2687 896 2689 897 2692 898 2698 899 2699 900 2701 901 2702 902 2704 903 2711 904 2713 905 2722 906 2723 907 2725 908 2726 909 2728 910 2732 911 2735 912 2737 913 2740 914 2744 915 2746 916 2747 917 2749 918 2750 919 2759 920 2761 921 2770 922 2771 923 2773 924 2774 925 2780 926 2783 927 2785 928 2788 929 2794 930 2795 931 2797 932 2798 933 2807 934 2809 935 2816 936 2818 937 2819 938 2821 939 2822 940 2824 941 2828 942 2831 943 2833 944 2836 945 2840 946 2842 947 2843 948 2845 949 2846 950 2848 951 2855 952 2857 953 2864 954 2866 955 2867 956 2869 957 2870 958 2876 959 2879 960 2881 961 2884 962 2890 963 2891 964 2893 965 2894 966 2896 967 2903 968 2905 969 2912 970 2914 971 2915 972 2917 973 2918 974 2920 975 2924 976 2927 977 2929 978 2932 979 2936 980 2938 981 2939 982 2941 983 2942 984 2951 985 2953 986 2962 987 2963 988 2965 989 2966 990 2972 991 2975 992 2977 993 2980 994 2986 995 2987 996 2989 997 2990 998 2999 999 3001 1000 3008 1001 3010 1002 3011 1003 3013 1004 3014 1005 3016 1006 3020 1007 3023 1008 3025 1009 3028 1010 3032 1011 3034 1012 3035 1013 3037 1014 3038 1015 3047 1016 3049 1017 3056 1018 3058 1019 3059 1020 3061 1021 3062 1022 3068 1023 3071 1024 3073 1025 3076 1026 3082 1027 3083 1028 3085 1029 3086 1030 3088 1031 3095 1032 3097 1033 3106 1034 3107 1035 3109 1036 3110 1037 3112 1038 3116 1039 3119 1040 3121 1041 3124 1042 3128 1043 3130 1044 3131 1045 3133 1046 3134 1047 3136 1048 3143 1049 3145 1050 3154 1051 3155 1052 3157 1053 3158 1054 3164 1055 3167 1056 3169 1057 3172 1058 3178 1059 3179 1060 3181 1061 3182 1062 3191 1063 3193 1064 3202 1065 3203 1066 3205 1067 3206 1068 3208 1069 3212 1070 3215 1071 3217 1072 3220 1073 3224 1074 3226 1075 3227 1076 3229 1077 3230 1078 3232 1079 3239 1080 3241 1081 3248 1082 3250 1083 3251 1084 3253 1085 3254 1086 3260 1087 3263 1088 3265 1089 3268 1090 3274 1091 3275 1092 3277 1093 3278 1094 3280 1095 3287 1096 3289 1097 3296 1098 3298 1099 3299 1100 3301 1101 3302 1102 3304 1103 3308 1104 3311 1105 3313 1106 3316 1107 3320 1108 3322 1109 3323 1110 3325 1111 3326 1112 3328 1113 3335 1114 3337 1115 3346 1116 3347 1117 3349 1118 3350 1119 3356 1120 3359 1121 3361 1122 3364 1123 3370 1124 3371 1125 3373 1126 3374 1127 3383 1128 3385 1129 3394 1130 3395 1131 3397 1132 3398 1133 3400 1134 3404 1135 3407 1136 3409 1137 3412 1138 3416 1139 3418 1140 3419 1141 3421 1142 3422 1143 3431 1144 3433 1145 3440 1146 3442 1147 3443 1148 3445 1149 3446 1150 3452 1151 3455 1152 3457 1153 3460 1154 3466 1155 3467 1156 3469 1157 3470 1158 3472 1159 3479 1160 3481 1161 3490 1162 3491 1163 3493 1164 3494 1165 3496 1166 3500 1167 3503 1168 3505 1169 3508 1170 3512 1171 3514 1172 3515 1173 3517 1174 3518 1175 3527 1176 3529 1177 3538 1178 3539 1179 3541 1180 3542 1181 3548 1182 3551 1183 3553 1184 3556 1185 3562 1186 3563 1187 3565 1188 3566 1189 3575 1190 3577 1191 3584 1192 3586 1193 3587 1194 3589 1195 3590 1196 3592 1197 3596 1198 3599 1199 3601 1200 3604 1201 3608 1202 3610 1203 3611 1204 3613 1205 3614 1206 3616 1207 3623 1208 3625 1209 3632 1210 3634 1211 3635 1212 3637 1213 3638 1214 3644 1215 3647 1216 3649 1217 3652 1218 3658 1219 3659 1220 3661 1221 3662 1222 3664 1223 3671 1224 3673 1225 3680 1226 3682 1227 3683 1228 3685 1229 3686 1230 3688 1231 3692 1232 3695 1233 3697 1234 3700 1235 3704 1236 3706 1237 3707 1238 3709 1239 3710 1240 3712 1241 3719 1242 3721 1243 3730 1244 3731 1245 3733 1246 3734 1247 3740 1248 3743 1249 3745 1250 3748 1251 3754 1252 3755 1253 3757 1254 3758 1255 3767 1256 3769 1257 3776 1258 3778 1259 3779 1260 3781 1261 3782 1262 3784 1263 3788 1264 3791 1265 3793 1266 3796 1267 3800 1268 3802 1269 3803 1270 3805 1271 3806 1272 3815 1273 3817 1274 3824 1275 3826 1276 3827 1277 3829 1278 3830 1279 3836 1280 3839 1281 3841 1282 3844 1283 3850 1284 3851 1285 3853 1286 3854 1287 3856 1288 3863 1289 3865 1290 3874 1291 3875 1292 3877 1293 3878 1294 3880 1295 3884 1296 3887 1297 3889 1298 3892 1299 3896 1300 3898 1301 3899 1302 3901 1303 3902 1304 3904 1305 3911 1306 3913 1307 3922 1308 3923 1309 3925 1310 3926 1311 3932 1312 3935 1313 3937 1314 3940 1315 3946 1316 3947 1317 3949 1318 3950 1319 3959 1320 3961 1321 3968 1322 3970 1323 3971 1324 3973 1325 3974 1326 3976 1327 3980 1328 3983 1329 3985 1330 3988 1331 3992 1332 3994 1333 3995 1334 3997 1335 3998 1336 4000 1337 4007 1338 4009 1339 4016 1340 4018 1341 4019 1342 4021 1343 4022 1344 4028 1345 4031 1346 4033 1347 4036 1348 4042 1349 4043 1350 4045 1351 4046 1352 4048 1353 4055 1354 4057 1355 4064 1356 4066 1357 4067 1358 4069 1359 4070 1360 4072 1361 4076 1362 4079 1363 4081 1364 4084 1365 4088 1366 4090 1367 4091 1368 4093 1369 4094 1370 4096 1371 4103 1372 4105 1373 4114 1374 4115 1375 4117 1376 4118 1377 4124 1378 4127 1379 4129 1380 4132 1381 4138 1382 4139 1383 4141 1384 4142 1385 4151 1386 4153 1387 4162 1388 4163 1389 4165 1390 4166 1391 4168 1392 4172 1393 4175 1394 4177 1395 4180 1396 4184 1397 4186 1398 4187 1399 4189 1400 4190 1401 4199 1402 4201 1403 4208 1404 4210 1405 4211 1406 4213 1407 4214 1408 4220 1409 4223 1410 4225 1411 4228 1412 4234 1413 4235 1414 4237 1415 4238 1416 4240 1417 4247 1418 4249 1419 4258 1420 4259 1421 4261 1422 4262 1423 4264 1424 4268 1425 4271 1426 4273 1427 4276 1428 4280 1429 4282 1430 4283 1431 4285 1432 4286 1433 4295 1434 4297 1435 4306 1436 4307 1437 4309 1438 4310 1439 4316 1440 4319 1441 4321 1442 4324 1443 4330 1444 4331 1445 4333 1446 4334 1447 4343 1448 4345 1449 4354 1450 4355 1451 4357 1452 4358 1453 4360 1454 4364 1455 4367 1456 4369 1457 4372 1458 4376 1459 4378 1460 4379 1461 4381 1462 4382 1463 4384 1464 4391 1465 4393 1466 4400 1467 4402 1468 4403 1469 4405 1470 4406 1471 4412 1472 4415 1473 4417 1474 4420 1475 4426 1476 4427 1477 4429 1478 4430 1479 4432 1480 4439 1481 4441 1482 4448 1483 4450 1484 4451 1485 4453 1486 4454 1487 4456 1488 4460 1489 4463 1490 4465 1491 4468 1492 4472 1493 4474 1494 4475 1495 4477 1496 4478 1497 4487 1498 4489 1499 4498 1500 4499 1501 4501 1502 4502 1503 4508 1504 4511 1505 4513 1506 4516 1507 4522 1508 4523 1509 4525 1510 4526 1511 4535 1512 4537 1513 4544 1514 4546 1515 4547 1516 4549 1517 4550 1518 4552 1519 4556 1520 4559 1521 4561 1522 4564 1523 4568 1524 4570 1525 4571 1526 4573 1527 4574 1528 4583 1529 4585 1530 4592 1531 4594 1532 4595 1533 4597 1534 4598 1535 4604 1536 4607 1537 4609 1538 4612 1539 4618 1540 4619 1541 4621 1542 4622 1543 4624 1544 4631 1545 4633 1546 4642 1547 4643 1548 4645 1549 4646 1550 4648 1551 4652 1552 4655 1553 4657 1554 4660 1555 4664 1556 4666 1557 4667 1558 4669 1559 4670 1560 4672 1561 4679 1562 4681 1563 4690 1564 4691 1565 4693 1566 4694 1567 4700 1568 4703 1569 4705 1570 4708 1571 4714 1572 4715 1573 4717 1574 4718 1575 4727 1576 4729 1577 4738 1578 4739 1579 4741 1580 4742 1581 4744 1582 4748 1583 4751 1584 4753 1585 4756 1586 4760 1587 4762 1588 4763 1589 4765 1590 4766 1591 4768 1592 4775 1593 4777 1594 4784 1595 4786 1596 4787 1597 4789 1598 4790 1599 4796 1600 4799 1601 4801 1602 4804 1603 4810 1604 4811 1605 4813 1606 4814 1607 4816 1608 4823 1609 4825 1610 4832 1611 4834 1612 4835 1613 4837 1614 4838 1615 4840 1616 4844 1617 4847 1618 4849 1619 4852 1620 4856 1621 4858 1622 4859 1623 4861 1624 4862 1625 4871 1626 4873 1627 4882 1628 4883 1629 4885 1630 4886 1631 4892 1632 4895 1633 4897 1634 4900 1635 4906 1636 4907 1637 4909 1638 4910 1639 4919 1640 4921 1641 4930 1642 4931 1643 4933 1644 4934 1645 4936 1646 4940 1647 4943 1648 4945 1649 4948 1650 4952 1651 4954 1652 4955 1653 4957 1654 4958 1655 4967 1656 4969 1657 4976 1658 4978 1659 4979 1660 4981 1661 4982 1662 4988 1663 4991 1664 4993 1665 4996