0  1 
 1  10 
 2  39 
 3  99 
 4  203 
 5  366 
 6  605 
 7  939 
 8  1389 
 9  1978 
 10  2731 
 11  3675 
 12  4839 
 13  6254 
 14  7953 
 15  9971 
 16  12345 
 17  15114 
 18  18319 
 19  22003 
 20  26211 
 21  30990 
 22  36389 
 23  42459 
 24  49253 
 25  56826 
 26  65235 
 27  74539 
 28  84799 
 29  96078 
 30  108441 
 31  121955 
 32  136689 
 33  152714 
 34  170103 
 35  188931 
 36  209275 
 37  231214 
 38  254829 
 39  280203 
 40  307421 
 41  336570 
 42  367739 
 43  401019 
 44  436503 
 45  474286 
 46  514465 
 47  557139 
 48  602409 
 49  650378 
 50  701151 
 51  754835 
 52  811539 
 53  871374 
 54  934453 
 55  1000891 
 56  1070805 
 57  1144314 
 58  1221539 
 59  1302603 
 60  1387631 
 61  1476750 
 62  1570089 
 63  1667779 
 64  1769953 
 65  1876746 
 66  1988295 
 67  2104739 
 68  2226219 
 69  2352878 
 70  2484861 
 71  2622315 
 72  2765389 
 73  2914234 
 74  3069003 
 75  3229851 
 76  3396935 
 77  3570414 
 78  3750449 
 79  3937203 
 80  4130841 
 81  4331530 
 82  4539439 
 83  4754739 
 84  4977603 
 85  5208206 
 86  5446725 
 87  5693339 
 88  5948229 
 89  6211578 
 90  6483571 
 91  6764395 
 92  7054239 
 93  7353294 
 94  7661753 
 95  7979811 
 96  8307665 
 97  8645514 
 98  8993559 
 99  9352003 
 100  9721051 
 101  10100910 
 102  10491789 
 103  10893899 
 104  11307453 
 105  11732666 
 106  12169755 
 107  12618939 
 108  13080439 
 109  13554478 
 110  14041281 
 111  14541075 
 112  15054089 
 113  15580554 
 114  16120703 
 115  16674771 
 116  17242995 
 117  17825614 
 118  18422869 
 119  19035003 
 120  19662261 
 121  20304890 
 122  20963139 
 123  21637259 
 124  22327503 
 125  23034126 
 126  23757385 
 127  24497539 
 128  25254849 
 129  26029578 
 130  26821991 
 131  27632355 
 132  28460939 
 133  29308014 
 134  30173853 
 135  31058731 
 136  31962925 
 137  32886714 
 138  33830379 
 139  34794203 
 140  35778471 
 141  36783470 
 142  37809489 
 143  38856819 
 144  39925753 
 145  41016586 
 146  42129615 
 147  43265139 
 148  44423459 
 149  45604878 
 150  46809701 
 151  48038235 
 152  49290789 
 153  50567674 
 154  51869203 
 155  53195691 
 156  54547455 
 157  55924814 
 158  57328089 
 159  58757603 
 160  60213681 
 161  61696650 
 162  63206839 
 163  64744579 
 164  66310203 
 165  67904046 
 166  69526445 
 167  71177739 
 168  72858269 
 169  74568378 
 170  76308411 
 171  78078715 
 172  79879639 
 173  81711534 
 174  83574753 
 175  85469651 
 176  87396585 
 177  89355914 
 178  91347999 
 179  93373203 
 180  95431891 
 181  97524430 
 182  99651189 
 183  101812539 
 184  104008853 
 185  106240506 
 186  108507875 
 187  110811339 
 188  113151279 
 189  115528078 
 190  117942121 
 191  120393795 
 192  122883489 
 193  125411594 
 194  127978503 
 195  130584611 
 196  133230315 
 197  135916014 
 198  138642109 
 199  141409003 
 200  144217101 
 201  147066810 
 202  149958539 
 203  152892699 
 204  155869703 
 205  158889966 
 206  161953905 
 207  165061939 
 208  168214489 
 209  171411978 
 210  174654831 
 211  177943475 
 212  181278339 
 213  184659854 
 214  188088453 
 215  191564571 
 216  195088645 
 217  198661114 
 218  202282419 
 219  205953003 
 220  209673311 
 221  213443790 
 222  217264889 
 223  221137059 
 224  225060753 
 225  229036426 
 226  233064535 
 227  237145539 
 228  241279899 
 229  245468078 
 230  249710541 
 231  254007755 
 232  258360189 
 233  262768314 
 234  267232603 
 235  271753531 
 236  276331575 
 237  280967214 
 238  285660929 
 239  290413203 
 240  295224521 
 241  300095370 
 242  305026239 
 243  310017619 
 244  315070003 
 245  320183886 
 246  325359765 
 247  330598139 
 248  335899509 
 249  341264378 
 250  346693251 
 251  352186635 
 252  357745039 
 253  363368974 
 254  369058953 
 255  374815491 
 256  380639105 
 257  386530314 
 258  392489639 
 259  398517603 
 260  404614731 
 261  410781550 
 262  417018589 
 263  423326379 
 264  429705453 
 265  436156346 
 266  442679595 
 267  449275739 
 268  455945319 
 269  462688878 
 270  469506961 
 271  476400115 
 272  483368889 
 273  490413834 
 274  497535503 
 275  504734451 
 276  512011235 
 277  519366414 
 278  526800549 
 279  534314203 
 280  541907941 
 281  549582330 
 282  557337939 
 283  565175339 
 284  573095103 
 285  581097806 
 286  589184025 
 287  597354339 
 288  605609329 
 289  613949578 
 290  622375671 
 291  630888195 
 292  639487739 
 293  648174894 
 294  656950253 
 295  665814411 
 296  674767965 
 297  683811514 
 298  692945659 
 299  702171003 
 300  711488151 
 301  720897710 
 302  730400289 
 303  739996499 
 304  749686953 
 305  759472266 
 306  769353055 
 307  779329939 
 308  789403539 
 309  799574478 
 310  809843381 
 311  820210875 
 312  830677589 
 313  841244154 
 314  851911203 
 315  862679371 
 316  873549295 
 317  884521614 
 318  895596969 
 319  906776003 
 320  918059361 
 321  929447690 
 322  940941639 
 323  952541859 
 324  964249003 
 325  976063726 
 326  987986685 
 327  1000018539 
 328  1012159949 
 329  1024411578 
 330  1036774091 
 331  1049248155 
 332  1061834439 
 333  1074533614 
 334  1087346353 
 335  1100273331 
 336  1113315225 
 337  1126472714 
 338  1139746479 
 339  1153137203 
 340  1166645571 
 341  1180272270 
 342  1194017989 
 343  1207883419 
 344  1221869253 
 345  1235976186 
 346  1250204915 
 347  1264556139 
 348  1279030559 
 349  1293628878 
 350  1308351801 
 351  1323200035 
 352  1338174289 
 353  1353275274 
 354  1368503703 
 355  1383860291 
 356  1399345755 
 357  1414960814 
 358  1430706189 
 359  1446582603 
 360  1462590781 
 361  1478731450 
 362  1495005339 
 363  1511413179 
 364  1527955703 
 365  1544633646 
 366  1561447745 
 367  1578398739 
 368  1595487369 
 369  1612714378 
 370  1630080511 
 371  1647586515 
 372  1665233139 
 373  1683021134 
 374  1700951253 
 375  1719024251 
 376  1737240885 
 377  1755601914 
 378  1774108099 
 379  1792760203 
 380  1811558991 
 381  1830505230 
 382  1849599689 
 383  1868843139 
 384  1888236353 
 385  1907780106 
 386  1927475175 
 387  1947322339 
 388  1967322379 
 389  1987476078 
 390  2007784221 
 391  2028247595 
 392  2048866989 
 393  2069643194 
 394  2090577003 
 395  2111669211 
 396  2132920615 
 397  2154332014 
 398  2175904209 
 399  2197638003 
 400  2219534201 
 401  2241593610 
 402  2263817039 
 403  2286205299 
 404  2308759203 
 405  2331479566 
 406  2354367205 
 407  2377422939 
 408  2400647589 
 409  2424041978 
 410  2447606931 
 411  2471343275 
 412  2495251839 
 413  2519333454 
 414  2543588953 
 415  2568019171 
 416  2592624945 
 417  2617407114 
 418  2642366519 
 419  2667504003 
 420  2692820411 
 421  2718316590 
 422  2743993389 
 423  2769851659 
 424  2795892253 
 425  2822116026 
 426  2848523835 
 427  2875116539 
 428  2901894999 
 429  2928860078 
 430  2956012641 
 431  2983353555 
 432  3010883689 
 433  3038603914 
 434  3066515103 
 435  3094618131 
 436  3122913875 
 437  3151403214 
 438  3180087029 
 439  3208966203 
 440  3238041621 
 441  3267314170 
 442  3296784739 
 443  3326454219 
 444  3356323503 
 445  3386393486 
 446  3416665065 
 447  3447139139 
 448  3477816609 
 449  3508698378 
 450  3539785351 
 451  3571078435 
 452  3602578539 
 453  3634286574 
 454  3666203453 
 455  3698330091 
 456  3730667405 
 457  3763216314 
 458  3795977739 
 459  3828952603 
 460  3862141831 
 461  3895546350 
 462  3929167089 
 463  3963004979 
 464  3997060953 
 465  4031335946 
 466  4065830895 
 467  4100546739 
 468  4135484419 
 469  4170644878 
 470  4206029061 
 471  4241637915 
 472  4277472389 
 473  4313533434 
 474  4349822003 
 475  4386339051 
 476  4423085535 
 477  4460062414 
 478  4497270649 
 479  4534711203 
 480  4572385041 
 481  4610293130 
 482  4648436439 
 483  4686815939 
 484  4725432603 
 485  4764287406 
 486  4803381325 
 487  4842715339 
 488  4882290429 
 489  4922107578 
 490  4962167771 
 491  5002471995 
 492  5043021239 
 493  5083816494 
 494  5124858753 
 495  5166149011 
 496  5207688265 
 497  5249477514 
 498  5291517759 
 499  5333810003 
 500  5376355251 
 501  5419154510 
 502  5462208789 
 503  5505519099 
 504  5549086453 
 505  5592911866 
 506  5636996355 
 507  5681340939 
 508  5725946639 
 509  5770814478 
 510  5815945481 
 511  5861340675 
 512  5907001089 
 513  5952927754 
 514  5999121703 
 515  6045583971 
 516  6092315595 
 517  6139317614 
 518  6186591069 
 519  6234137003 
 520  6281956461 
 521  6330050490 
 522  6378420139 
 523  6427066459 
 524  6475990503 
 525  6525193326 
 526  6574675985 
 527  6624439539 
 528  6674485049 
 529  6724813578 
 530  6775426191 
 531  6826323955 
 532  6877507939 
 533  6928979214 
 534  6980738853 
 535  7032787931 
 536  7085127525 
 537  7137758714 
 538  7190682579 
 539  7243900203 
 540  7297412671 
 541  7351221070 
 542  7405326489 
 543  7459730019 
 544  7514432753 
 545  7569435786 
 546  7624740215 
 547  7680347139 
 548  7736257659 
 549  7792472878 
 550  7848993901 
 551  7905821835 
 552  7962957789 
 553  8020402874 
 554  8078158203 
 555  8136224891 
 556  8194604055 
 557  8253296814 
 558  8312304289 
 559  8371627603 
 560  8431267881 
 561  8491226250 
 562  8551503839 
 563  8612101779 
 564  8673021203 
 565  8734263246 
 566  8795829045 
 567  8857719739 
 568  8919936469 
 569  8982480378 
 570  9045352611 
 571  9108554315 
 572  9172086639 
 573  9235950734 
 574  9300147753 
 575  9364678851 
 576  9429545185 
 577  9494747914 
 578  9560288199 
 579  9626167203 
 580  9692386091 
 581  9758946030 
 582  9825848189 
 583  9893093739 
 584  9960683853 
 585  10028619706 
 586  10096902475 
 587  10165533339 
 588  10234513479 
 589  10303844078 
 590  10373526321 
 591  10443561395 
 592  10513950489 
 593  10584694794 
 594  10655795503 
 595  10727253811 
 596  10799070915 
 597  10871248014 
 598  10943786309 
 599  11016687003 
 600  11089951301 
 601  11163580410 
 602  11237575539 
 603  11311937899 
 604  11386668703 
 605  11461769166 
 606  11537240505 
 607  11613083939 
 608  11689300689 
 609  11765891978 
 610  11842859031 
 611  11920203075 
 612  11997925339 
 613  12076027054 
 614  12154509453 
 615  12233373771 
 616  12312621245 
 617  12392253114 
 618  12472270619 
 619  12552675003 
 620  12633467511 
 621  12714649390 
 622  12796221889 
 623  12878186259 
 624  12960543753 
 625  13043295626 
 626  13126443135 
 627  13209987539 
 628  13293930099 
 629  13378272078 
 630  13463014741 
 631  13548159355 
 632  13633707189 
 633  13719659514 
 634  13806017603 
 635  13892782731 
 636  13979956175 
 637  14067539214 
 638  14155533129 
 639  14243939203 
 640  14332758721 
 641  14421992970 
 642  14511643239 
 643  14601710819 
 644  14692197003 
 645  14783103086 
 646  14874430365 
 647  14966180139 
 648  15058353709 
 649  15150952378 
 650  15243977451 
 651  15337430235 
 652  15431312039 
 653  15525624174 
 654  15620367953 
 655  15715544691 
 656  15811155705 
 657  15907202314 
 658  16003685839 
 659  16100607603 
 660  16197968931 
 661  16295771150 
 662  16394015589 
 663  16492703579 
 664  16591836453 
 665  16691415546 
 666  16791442195 
 667  16891917739 
 668  16992843519 
 669  17094220878 
 670  17196051161 
 671  17298335715 
 672  17401075889 
 673  17504273034 
 674  17607928503 
 675  17712043651 
 676  17816619835 
 677  17921658414 
 678  18027160749 
 679  18133128203 
 680  18239562141 
 681  18346463930 
 682  18453834939 
 683  18561676539 
 684  18669990103 
 685  18778777006 
 686  18888038625 
 687  18997776339 
 688  19107991529 
 689  19218685578 
 690  19329859871 
 691  19441515795 
 692  19553654739 
 693  19666278094 
 694  19779387253 
 695  19892983611 
 696  20007068565 
 697  20121643514 
 698  20236709859 
 699  20352269003 
 700  20468322351 
 701  20584871310 
 702  20701917289 
 703  20819461699 
 704  20937505953 
 705  21056051466 
 706  21175099655 
 707  21294651939 
 708  21414709739 
 709  21535274478 
 710  21656347581 
 711  21777930475 
 712  21900024589 
 713  22022631354 
 714  22145752203 
 715  22269388571 
 716  22393541895 
 717  22518213614 
 718  22643405169 
 719  22769118003 
 720  22895353561 
 721  23022113290 
 722  23149398639 
 723  23277211059 
 724  23405552003 
 725  23534422926 
 726  23663825285 
 727  23793760539 
 728  23924230149 
 729  24055235578 
 730  24186778291 
 731  24318859755 
 732  24451481439 
 733  24584644814 
 734  24718351353 
 735  24852602531 
 736  24987399825 
 737  25122744714 
 738  25258638679 
 739  25395083203 
 740  25532079771 
 741  25669629870 
 742  25807734989 
 743  25946396619 
 744  26085616253 
 745  26225395386 
 746  26365735515 
 747  26506638139 
 748  26648104759 
 749  26790136878 
 750  26932736001 
 751  27075903635 
 752  27219641289 
 753  27363950474 
 754  27508832703 
 755  27654289491 
 756  27800322355 
 757  27946932814 
 758  28094122389 
 759  28241892603 
 760  28390244981 
 761  28539181050 
 762  28688702339 
 763  28838810379 
 764  28989506703 
 765  29140792846 
 766  29292670345 
 767  29445140739 
 768  29598205569 
 769  29751866378 
 770  29906124711 
 771  30060982115 
 772  30216440139 
 773  30372500334 
 774  30529164253 
 775  30686433451 
 776  30844309485 
 777  31002793914 
 778  31161888299 
 779  31321594203 
 780  31481913191 
 781  31642846830 
 782  31804396689 
 783  31966564339 
 784  32129351353 
 785  32292759306 
 786  32456789775 
 787  32621444339 
 788  32786724579 
 789  32952632078 
 790  33119168421 
 791  33286335195 
 792  33454133989 
 793  33622566394 
 794  33791634003 
 795  33961338411 
 796  34131681215 
 797  34302664014 
 798  34474288409 
 799  34646556003 
 800  34819468401 
 801  34993027210 
 802  35167234039 
 803  35342090499 
 804  35517598203 
 805  35693758766 
 806  35870573805 
 807  36048044939 
 808  36226173789 
 809  36404961978 
 810  36584411131 
 811  36764522875 
 812  36945298839 
 813  37126740654 
 814  37308849953 
 815  37491628371 
 816  37675077545 
 817  37859199114 
 818  38043994719 
 819  38229466003 
 820  38415614611 
 821  38602442190 
 822  38789950389 
 823  38978140859 
 824  39167015253 
 825  39356575226 
 826  39546822435 
 827  39737758539 
 828  39929385199 
 829  40121704078 
 830  40314716841 
 831  40508425155 
 832  40702830689 
 833  40897935114 
 834  41093740103 
 835  41290247331 
 836  41487458475 
 837  41685375214 
 838  41883999229 
 839  42083332203 
 840  42283375821 
 841  42484131770 
 842  42685601739 
 843  42887787419 
 844  43090690503 
 845  43294312686 
 846  43498655665 
 847  43703721139 
 848  43909510809 
 849  44116026378 
 850  44323269551 
 851  44531242035 
 852  44739945539 
 853  44949381774 
 854  45159552453 
 855  45370459291 
 856  45582104005 
 857  45794488314 
 858  46007613939 
 859  46221482603 
 860  46436096031 
 861  46651455950 
 862  46867564089 
 863  47084422179 
 864  47302031953 
 865  47520395146 
 866  47739513495 
 867  47959388739 
 868  48180022619 
 869  48401416878 
 870  48623573261 
 871  48846493515 
 872  49070179389 
 873  49294632634 
 874  49519855003 
 875  49745848251 
 876  49972614135 
 877  50200154414 
 878  50428470849 
 879  50657565203 
 880  50887439241 
 881  51118094730 
 882  51349533439 
 883  51581757139 
 884  51814767603 
 885  52048566606 
 886  52283155925 
 887  52518537339 
 888  52754712629 
 889  52991683578 
 890  53229451971 
 891  53468019595 
 892  53707388239 
 893  53947559694 
 894  54188535753 
 895  54430318211 
 896  54672908865 
 897  54916309514 
 898  55160521959 
 899  55405548003 
 900  55651389451 
 901  55898048110 
 902  56145525789 
 903  56393824299 
 904  56642945453 
 905  56892891066 
 906  57143662955 
 907  57395262939 
 908  57647692839 
 909  57900954478 
 910  58155049681 
 911  58409980275 
 912  58665748089 
 913  58922354954 
 914  59179802703 
 915  59438093171 
 916  59697228195 
 917  59957209614 
 918  60218039269 
 919  60479719003 
 920  60742250661 
 921  61005636090 
 922  61269877139 
 923  61534975659 
 924  61800933503 
 925  62067752526 
 926  62335434585 
 927  62603981539 
 928  62873395249 
 929  63143677578 
 930  63414830391 
 931  63686855555 
 932  63959754939 
 933  64233530414 
 934  64508183853 
 935  64783717131 
 936  65060132125 
 937  65337430714 
 938  65615614779 
 939  65894686203 
 940  66174646871 
 941  66455498670 
 942  66737243489 
 943  67019883219 
 944  67303419753 
 945  67587854986 
 946  67873190815 
 947  68159429139 
 948  68446571859 
 949  68734620878 
 950  69023578101 
 951  69313445435 
 952  69604224789 
 953  69895918074 
 954  70188527203 
 955  70482054091 
 956  70776500655 
 957  71071868814 
 958  71368160489 
 959  71665377603 
 960  71963522081 
 961  72262595850 
 962  72562600839 
 963  72863538979 
 964  73165412203 
 965  73468222446 
 966  73771971645 
 967  74076661739 
 968  74382294669 
 969  74688872378 
 970  74996396811 
 971  75304869915 
 972  75614293639 
 973  75924669934 
 974  76236000753 
 975  76548288051 
 976  76861533785 
 977  77175739914 
 978  77490908399 
 979  77807041203 
 980  78124140291 
 981  78442207630 
 982  78761245189 
 983  79081254939 
 984  79402238853 
 985  79724198906 
 986  80047137075 
 987  80371055339 
 988  80695955679 
 989  81021840078 
 990  81348710521 
 991  81676568995 
 992  82005417489 
 993  82335257994 
 994  82666092503 
 995  82997923011 
 996  83330751515 
 997  83664580014 
 998  83999410509 
 999  84335245003 
 1000  84672085501