1000
3 5 7 10 10 8 10 12 15 16 17 19 20 21 24 24 25 26 73 31 35 36 37 38 39 39 40 41 46 64 68 189717 85 98 115 122 137 3738453 190 196 206 222 225 234 241 251 263 276 277 282 284 303 307 310 317 319 328 337 342 365 371 374 393 414 417 421 437 554 582 645 654 778 886 940 1109 1272 1331 1345 1364 1443 1489 1641 1711 1724 1818 1828 1897 1952 1962 2262 2279 2381 2381 2411 2590 2677 2681 2699 2706 2718 2755 2984 3003 3028 3269 3284 3370 3428 3470 3644 3707 3720 3741 3792 554627 3813 3875 3926 3975 4030 4072 4159 4204 4289 4332 4408 4579 4930 4991 5367 5979 6203 6376 6801 7146 7302 7428 7698 8028 8560 8617 9033 99714 9394 9450 9818 10024 10262 10658 10995 11241 11634 12694 12812 13153 14016 14555 14577 14606 14757 15114 15131 15677 1577829 16290 16448 16729 16941 17125 17210 2118554 17665 18038 18058 18063 18510 18971 19276 20076 20173 20260 20334 172067 21189 21796 21994 21995 22420 22565 22943 23238 23966 23999 24153 24711 25789 26312 26628 26836 26874 26897 27238 27776 28109 28279 28500 28803 29441 29756 29992 30165 31049 32038 32044 32166 32179 32559 32613 32660 32741 33161 33281 33431 33893 33940 34311 34770 34894 35730 36125 36435 36661 36790 37338 37814 38330 38344 38592 38667 39242 39287 39531 39875 39918 40117 40135 40909 41007 41348 41758 42194 45545 45692 45879 45922 46380 48067 48086 49876 50205 3185978 53371 54537 55286 55888 56647 60660 63096 63241 64319 65765 65987 67615 69523 71555 74324 1599468 75866 2193298 80617 81853 83380 83646 84465 84737 84798 85516 86889 88011 88156 90672 91003 93093 96913 97295 97346 98468 99284 99599 9392 99756 104371 105176 106315 106728 108353 109991 110256 111100 113826 114508 114581 119136 119948 120287 409814 121872 123723 124458 124893 124971 125355 125733 128099 129433 130189 131203 132198 132502 133565 133992 134947 135139 136126 138921 139256 141143 142627 148560 149071 151584 153081 155214 155810 155922 156414 156455 156509 156678 156689 161340 161408 165653 166917 169036 170537 170566 170757 170913 20585 172108 173171 174501 179124 180807 181639 182424 183675 185951 186399 2686514 189427 189509 31 189917 189928 190234 191383 192961 193642 194740 196971 197465 203856 208879 215214 215995 219320 221337 222161 228185 228473 228655 228858 229058 229205 231200 232569 232765 233395 2876294 241121 242503 2191351 246780 2885463 254253 254564 259520 262772 267303 269827 271630 274006 274636 276210 276465 276573 280329 280409 281915 282419 283681 285164 291309 293657 294811 295347 300146 300159 300183 300208 300723 302757 303006 303120 305920 306260 306496 309561 312741 314420 3794255 320409 320424 320575 322929 323740 323767 323889 325949 326130 326430 327010 327868 327877 330695 330897 331845 333487 334379 336851 337863 338324 338519 340163 341641 342210 342624 344131 346364 348124 350445 351687 353014 355440 355969 356336 357203 357860 357953 359837 360976 364118 366511 368151 369714 370060 370379 371504 372353 374123 375571 379022 382541 382682 385830 386258 386877 386880 387062 388461 389973 391269 392514 393174 394054 395818 398830 399603 400382 401213 403305 403323 403326 403442 404302 404605 404836 407514 120720 413619 414069 415358 2048946 422116 423911 425095 425100 427170 427404 429190 4165679 433274 437730 439023 443934 451763 461729 493243 505233 508362 511086 515460 520531 521201 534726 540091 3798 559663 567545 572353 575841 576965 585124 597275 599111 602200 602866 618101 622409 17409 637353 643634 645932 646521 665114 688829 692544 698117 714995 726322 731845 731965 732744 738822 750454 752896 764955 2570637 794593 797053 799955 814400 818137 818655 827439 845416 849411 773552 4163093 881101 888300 897115 897917 936140 949719 978165 986032 987560 989306 996516 1005435 1008216 1016777 1018140 1022241 1037982 1059357 1064513 1065166 1069318 1079753 1083453 1094473 1103872 1110861 1119175 1119632 1124012 1132324 1135760 1135893 1162547 1163311 1181030 1185219 1194026 1195047 1204367 1204921 1208367 1210980 1214477 1227007 1239617 1241849 1244430 1247849 1268550 1273818 1274268 1274905 1277370 1279588 1289162 1299944 1300291 1312906 1338839 1349001 1350370 1377248 1401907 1414601 1416966 1421871 1443918 1457352 1460632 1464388 1468135 1478194 1484438 1487322 1492783 1495091 1498728 1503829 1507062 1508540 1566075 1572730 15697 1579144 1586175 1590134 75462 1609759 1615210 1620307 1634320 1635201 1656906 1665316 1672350 1680142 1686340 1696088 1698038 1701536 1702156 1708156 1711422 1727507 1732896 1738811 1742880 1771224 1780154 1786262 1790751 1798644 1803425 1808761 1808911 1809431 1814775 1825295 1831926 1837810 1844568 1845982 1849843 1864846 1865194 1882585 1912958 1914414 1918590 1925715 1930528 1947390 1953922 1963637 1983737 1985525 1991175 1994497 2044020 415377 2073465 2084800 2089557 2091425 2093634 2100130 2112683 622592 2127451 2128422 2128789 2134291 2138365 2142511 2146730 2167831 2170953 2182676 2182872 2182947 245253 77691 2195461 2205702 2211025 2242586 2258684 2260325 2260977 2264583 2280390 2284135 2313437 2315260 2320387 2331824 2334663 2335597 2351806 2386173 2388116 2392597 2395185 2399769 2431695 2435352 2442137 2447522 2450984 2463869 2464827 2490029 2502640 2519132 2536448 2539550 2541984 2542821 2551043 2562991 2567322 876203 2589941 2591102 2591800 2619927 2629295 2634314 2634888 2637417 2639915 2646106 2651082 2652858 2671326 2682884 188817 2730639 2731145 2734784 2747206 2748596 2749004 2752010 2758988 2763796 2765134 2768843 2787677 2789304 2809561 2831242 2843132 2844895 2848180 2851143 2857693 2861704 236305 2877773 2878321 248294 2890300 2915330 2929762 2941241 2941585 2957112 2958128 2963719 3004357 3005439 3012262 3013915 3016835 3020345 3039830 3058506 3058802 3079007 3090906 3093914 3101045 3110008 3112969 3140445 3141323 3152338 3177722 3179432 3184738 51708 3200182 3216517 3216805 3219234 3232554 3239562 3250335 3253704 3257444 3258377 3262750 3271952 3273860 3290001 3299134 3301265 3324928 3334970 3340556 3358917 3371563 3371881 3373195 3379386 3384002 3391641 3395614 3407522 3409148 3413154 3419533 3436181 3470457 3471295 3482086 3484038 3496946 3498572 3505482 3508962 3509009 3511564 3514384 3540668 3554635 3563846 3582226 3605696 3626977 3646314 3646409 3657346 3667365 3688275 3702489 3726642 3730033 3737903 3737945 185 3759110 3761176 3777108 3782972 3791231 317314 3794652 3799604 3800874 3816158 3825261 3827105 3827205 3828113 3842186 3847228 3857338 3876640 3880007 3881892 3881971 3895634 3897377 3914053 3916232 3919993 3920517 3926880 3942800 3948380 3967567 3969571 3974876 3980676 3985044 3985821 3987425 3987696 3988645 4008684 4024817 4029335 4052828 4055893 4060274 4066561 4074111 4084648 4086317 4111673 4113264 4120326 4120770 4129503 4132238 4140583 4145406 4162728 877400 429899 4186149 4190469 4201951 4207513 4210389 4220320 4223607 4224170 4224223 4241441 4242080 4242985 4245458 4251412 4253671 4262892 4285668