1 1
2 70
3 639
4 2716
5 7885
6 18306
7 36715
8 66424
9 111321
10 175870
11 265111
12 384660
13 540709
14 740026
15 989955
16 1298416
17 1673905
18 2125494
19 2662831
20 3296140
21 4036221
22 4894450
23 5882779
24 7013736
25 8300425
26 9756526
27 11396295
28 13234564
29 15286741
30 17568810
31 20097331
32 22889440
33 25962849
34 29335846
35 33027295
36 37056636
37 41443885
38 46209634
39 51375051
40 56961880
41 62992441
42 69489630
43 76476919
44 83978356
45 92018565
46 100622746
47 109816675
48 119626704
49 130079761
50 141203350
51 153025551
52 165575020
53 178880989
54 192973266
55 207882235
56 223638856
57 240274665
58 257821774
59 276312871
60 295781220
61 316260661
62 337785610
63 360391059
64 384112576
65 408986305
66 435048966
67 462337855
68 490890844
69 520746381
70 551943490
71 584521771
72 618521400
73 653983129
74 690948286
75 729458775
76 769557076
77 811286245
78 854689914
79 899812291
80 946698160
81 995392881
82 1045942390
83 1098393199
84 1152792396
85 1209187645
86 1267627186
87 1328159835
88 1390834984
89 1455702601
90 1522813230
91 1592217991
92 1663968580
93 1738117269
94 1814716906
95 1893820915
96 1975483296
97 2059758625
98 2146702054
99 2236369311
100 2328816700
101 2424101101
102 2522279970
103 2623411339
104 2727553816
105 2834766585
106 2945109406
107 3058642615
108 3175427124
109 3295524421
110 3418996570
111 3545906211
112 3676316560
113 3810291409
114 3947895126
115 4089192655
116 4234249516
117 4383131805
118 4535906194
119 4692639931
120 4853400840
121 5018257321
122 5187278350
123 5360533479
124 5538092836
125 5720027125
126 5906407626
127 6097306195
128 6292795264
129 6492947841
130 6697837510
131 6907538431
132 7122125340
133 7341673549
134 7566258946
135 7795957995
136 8030847736
137 8271005785
138 8516510334
139 8767440151
140 9023874580
141 9285893541
142 9553577530
143 9827007619
144 10106265456
145 10391433265
146 10682593846
147 10979830575
148 11283227404
149 11592868861
150 11908840050
151 12231226651
152 12560114920
153 12895591689
154 13237744366
155 13586660935
156 13942429956
157 14305140565
158 14674882474
159 15051745971
160 15435821920
161 15827201761
162 16225977510
163 16632241759
164 17046087676
165 17467609005
166 17896900066
167 18334055755
168 18779171544
169 19232343481
170 19693668190
171 20163242871
172 20641165300
173 21127533829
174 21622447386
175 22126005475
176 22638308176
177 23159456145
178 23689550614
179 24228693391
180 24776986860
181 25334533981
182 25901438290
183 26477803899
184 27063735496
185 27659338345
186 28264718286
187 28879981735
188 29505235684
189 30140587701
190 30786145930
191 31442019091
192 32108316480
193 32785147969
194 33472624006
195 34170855615
196 34879954396
197 35600032525
198 36331202754
199 37073578411
200 37827273400
201 38592402201
202 39369079870
203 40157422039
204 40957544916
205 41769565285
206 42593600506
207 43429768515
208 44278187824
209 45138977521
210 46012257270
211 46898147311
212 47796768460
213 48708242109
214 49632690226
215 50570235355
216 51521000616
217 52485109705
218 53462686894
219 54453857031
220 55458745540
221 56477478421
222 57510182250
223 58556984179
224 59618011936
225 60693393825
226 61783258726
227 62887736095
228 64006955964
229 65141048941
230 66290146210
231 67454379531
232 68633881240
233 69828784249
234 71039222046
235 72265328695
236 73507238836
237 74765087685
238 76039011034
239 77329145251
240 78635627280
241 79958594641
242 81298185430
243 82654538319
244 84027792556
245 85418087965
246 86825564946
247 88250364475
248 89692628104
249 91152497961
250 92630116750
251 94125627751
252 95639174820
253 97170902389
254 98720955466
255 100289479635
256 101876621056
257 103482526465
258 105107343174
259 106751219071
260 108414302620
261 110096742861
262 111798689410
263 113520292459
264 115261702776
265 117023071705
266 118804551166
267 120606293655
268 122428452244
269 124271180581
270 126134632890
271 128018963971
272 129924329200
273 131850884529
274 133798786486
275 135768192175
276 137759259276
277 139772146045
278 141807011314
279 143864014491
280 145943315560
281 148045075081
282 150169454190
283 152316614599
284 154486718596
285 156679929045
286 158896409386
287 161136323635
288 163399836384
289 165687112801
290 167998318630
291 170333620191
292 172693184380
293 175077178669
294 177485771106
295 179919130315
296 182377425496
297 184860826425
298 187369503454
299 189903627511
300 192463370100
301 195048903301
302 197660399770
303 200298032739
304 202961976016
305 205652403985
306 208369491606
307 211113414415
308 213884348524
309 216682470621
310 219507957970
311 222360988411
312 225241740360
313 228150392809
314 231087125326
315 234052118055
316 237045551716
317 240067607605
318 243118467594
319 246198314131
320 249307330240
321 252445699521
322 255613606150
323 258811234879
324 262038771036
325 265296400525
326 268584309826
327 271902685995
328 275251716664
329 278631590041
330 282042494910
331 285484620631
332 288958157140
333 292463294949
334 296000225146
335 299569139395
336 303170229936
337 306803689585
338 310469711734
339 314168490351
340 317900219980
341 321665095741
342 325463313330
343 329295069019
344 333160559656
345 337059982665
346 340993536046
347 344961418375
348 348963828804
349 353000967061
350 357073033450
351 361180228851
352 365322754720
353 369500813089
354 373714606566
355 377964338335
356 382250212156
357 386572432365
358 390931203874
359 395326732171
360 399759223320
361 404228883961
362 408735921310
363 413280543159
364 417862957876
365 422483374405
366 427142002266
367 431839051555
368 436574732944
369 441349257681
370 446162837590
371 451015685071
372 455908013100
373 460840035229
374 465811965586
375 470824018875
376 475876410376
377 480969355945
378 486103072014
379 491277775591
380 496493684260
381 501751016181
382 507049990090
383 512390825299
384 517773741696
385 523198959745
386 528666700486
387 534177185535
388 539730637084
389 545327277901
390 550967331330
391 556651021291
392 562378572280
393 568150209369
394 573966158206
395 579826645015
396 585731896596
397 591682140325
398 597677604154
399 603718516611
400 609805106800
401 615937604401
402 622116239670
403 628341243439
404 634612847116
405 640931282685
406 647296782706
407 653709580315
408 660169909224
409 666678003721
410 673234098670
411 679838429511
412 686491232260
413 693192743509
414 699943200426
415 706742840755
416 713591902816
417 720490625505
418 727439248294
419 734438011231
420 741487154940
421 748586920621
422 755737550050
423 762939285579
424 770192370136
425 777497047225
426 784853560926
427 792262155895
428 799723077364
429 807236571141
430 814802883610
431 822422261731
432 830094953040
433 837821205649
434 845601268246
435 853435390095
436 861323821036
437 869266811485
438 877264612434
439 885317475451
440 893425652680
441 901589396841
442 909808961230
443 918084599719
444 926416566756
445 934805117365
446 943250507146
447 951752992275
448 960312829504
449 968930276161
450 977605590150
451 986339029951
452 995130854620
453 1003981323789
454 1012890697666
455 1021859237035
456 1030887203256
457 1039974858265
458 1049122464574
459 1058330285271
460 1067598584020
461 1076927625061
462 1086317673210
463 1095768993859
464 1105281852976
465 1114856517105
466 1124493253366
467 1134192329455
468 1143954013644
469 1153778574781
470 1163666282290
471 1173617406171
472 1183632217000
473 1193710985929
474 1203853984686
475 1214061485575
476 1224333761476
477 1234671085845
478 1245073732714
479 1255541976691
480 1266076092960
481 1276676357281
482 1287343045990
483 1298076435999
484 1308876804796
485 1319744430445
486 1330679591586
487 1341682567435
488 1352753637784
489 1363893083001
490 1375101184030
491 1386378222391
492 1397724480180
493 1409140240069
494 1420625785306
495 1432181399715
496 1443807367696
497 1455503974225
498 1467271504854
499 1479110245711
500 1491020483500
501 1503002505501
502 1515056599570
503 1527183054139
504 1539382158216
505 1551654201385
506 1563999473806
507 1576418266215
508 1588910869924
509 1601477576821
510 1614118679370
511 1626834470611
512 1639625244160
513 1652491294209
514 1665432915526
515 1678450403455
516 1691544053916
517 1704714163405
518 1717961028994
519 1731284948331
520 1744686219640
521 1758165141721
522 1771722013950
523 1785357136279
524 1799070809236
525 1812863333925
526 1826735012026
527 1840686145795
528 1854717038064
529 1868827992241
530 1883019312310
531 1897291302831
532 1911644268940
533 1926078516349
534 1940594351346
535 1955192080795
536 1969872012136
537 1984634453385
538 1999479713134
539 2014408100551
540 2029419925380
541 2044515497941
542 2059695129130
543 2074959130419
544 2090307813856
545 2105741492065
546 2121260478246
547 2136865086175
548 2152555630204
549 2168332425261
550 2184195786850
551 2200146031051
552 2216183474520
553 2232308434489
554 2248521228766
555 2264822175735
556 2281211594356
557 2297689804165
558 2314257125274
559 2330913878371
560 2347660384720
561 2364496966161
562 2381423945110
563 2398441644559
564 2415550388076
565 2432750499805
566 2450042304466
567 2467426127355
568 2484902294344
569 2502471131881
570 2520132966990
571 2537888127271
572 2555736940900
573 2573679736629
574 2591716843786
575 2609848592275
576 2628075312576
577 2646397335745
578 2664814993414
579 2683328617791
580 2701938541660
581 2720645098381
582 2739448621890
583 2758349446699
584 2777347907896
585 2796444341145
586 2815639082686
587 2834932469335
588 2854324838484
589 2873816528101
590 2893407876730
591 2913099223491
592 2932890908080
593 2952783270769
594 2972776652406
595 2992871394415
596 3013067838796
597 3033366328125
598 3053767205554
599 3074270814811
600 3094877500200
601 3115587606601
602 3136401479470
603 3157319464839
604 3178341909316
605 3199469160085
606 3220701564906
607 3242039472115
608 3263483230624
609 3285033189921
610 3306689700070
611 3328453111711
612 3350323776060
613 3372302044909
614 3394388270626
615 3416582806155
616 3438886005016
617 3461298221305
618 3483819809694
619 3506451125431
620 3529192524340
621 3552044362821
622 3575006997850
623 3598080786979
624 3621266088336
625 3644563260625
626 3667972663126
627 3691494655695
628 3715129598764
629 3738877853341
630 3762739781010
631 3786715743931
632 3810806104840
633 3835011227049
634 3859331474446
635 3883767211495
636 3908318803236
637 3932986615285
638 3957771013834
639 3982672365651
640 4007691038080
641 4032827399041
642 4058081817030
643 4083454661119
644 4108946300956
645 4134557106765
646 4160287449346
647 4186137700075
648 4212108230904
649 4238199414361
650 4264411623550
651 4290745232151
652 4317200614420
653 4343778145189
654 4370478199866
655 4397301154435
656 4424247385456
657 4451317270065
658 4478511185974
659 4505829511471
660 4533272625420
661 4560840907261
662 4588534737010
663 4616354495259
664 4644300563176
665 4672373322505
666 4700573155566
667 4728900445255
668 4757355575044
669 4785938928981
670 4814650891690
671 4843491848371
672 4872462184800
673 4901562287329
674 4930792542886
675 4960153338975
676 4989645063676
677 5019268105645
678 5049022854114
679 5078909698891
680 5108929030360
681 5139081239481
682 5169366717790
683 5199785857399
684 5230339050996
685 5261026691845
686 5291849173786
687 5322806891235
688 5353900239184
689 5385129613201
690 5416495409430
691 5447998024591
692 5479637855980
693 5511415301469
694 5543330759506
695 5575384629115
696 5607577309896
697 5639909202025
698 5672380706254
699 5704992223911
700 5737744156900
701 5770636907701
702 5803670879370
703 5836846475539
704 5870164100416
705 5903624158785
706 5937227056006
707 5970973198015
708 6004862991324
709 6038896843021
710 6073075160770
711 6107398352811
712 6141866827960
713 6176480995609
714 6211241265726
715 6246148048855
716 6281201756116
717 6316402799205
718 6351751590394
719 6387248542531
720 6422894069040
721 6458688583921
722 6494632501750
723 6530726237679
724 6566970207436
725 6603364827325
726 6639910514226
727 6676607685595
728 6713456759464
729 6750458154441
730 6787612289710
731 6824919585031
732 6862380460740
733 6899995337749
734 6937764637546
735 6975688782195
736 7013768194336
737 7052003297185
738 7090394514534
739 7128942270751
740 7167646990780
741 7206509100141
742 7245529024930
743 7284707191819
744 7324044028056
745 7363539961465
746 7403195420446
747 7443010833975
748 7482986631604
749 7523123243461
750 7563421100250
751 7603880633251
752 7644502274320
753 7685286455889
754 7726233610966
755 7767344173135
756 7808618576556
757 7850057255965
758 7891660646674
759 7933429184571
760 7975363306120
761 8017463448361
762 8059730048910
763 8102163545959
764 8144764378276
765 8187532985205
766 8230469806666
767 8273575283155
768 8316849855744
769 8360293966081
770 8403908056390
771 8447692569471
772 8491647948700
773 8535774638029
774 8580073081986
775 8624543725675
776 8669187014776
777 8714003395545
778 8758993314814
779 8804157219991
780 8849495559060
781 8895008780581
782 8940697333690
783 8986561668099
784 9032602234096
785 9078819482545
786 9125213864886
787 9171785833135
788 9218535839884
789 9265464338301
790 9312571782130
791 9359858625691
792 9407325323880
793 9454972332169
794 9502800106606
795 9550809103815
796 9598999780996
797 9647372595925
798 9695928006954
799 9744666473011
800 9793588453600
801 9842694408801
802 9891984799270
803 9941460086239
804 9991120731516
805 10040967197485
806 10090999947106
807 10141219443915
808 10191626152024
809 10242220536121
810 10293003061470
811 10343974193911
812 10395134399860
813 10446484146309
814 10498023900826
815 10549754131555
816 10601675307216
817 10653787897105
818 10706092371094
819 10758589199631
820 10811278853740
821 10864161805021
822 10917238525650
823 10970509488379
824 11023975166536
825 11077636034025
826 11131492565326
827 11185545235495
828 11239794520164
829 11294240895541
830 11348884838410
831 11403726826131
832 11458767336640
833 11514006848449
834 11569445840646
835 11625084792895
836 11680924185436
837 11736964499085
838 11793206215234
839 11849649815851
840 11906295783480
841 11963144601241
842 12020196752830
843 12077452722519
844 12134912995156
845 12192578056165
846 12250448391546
847 12308524487875
848 12366806832304
849 12425295912561
850 12483992216950
851 12542896234351
852 12602008454220
853 12661329366589
854 12720859462066
855 12780599231835
856 12840549167656
857 12900709761865
858 12961081507374
859 13021664897671
860 13082460426820
861 13143468589461
862 13204689880810
863 13266124796659
864 13327773833376
865 13389637487905
866 13451716257766
867 13514010641055
868 13576521136444
869 13639248243181
870 13702192461090
871 13765354290571
872 13828734232600
873 13892332788729
874 13956150461086
875 14020187752375
876 14084445165876
877 14148923205445
878 14213622375514
879 14278543181091
880 14343686127760
881 14409051721681
882 14474640469590
883 14540452878799
884 14606489457196
885 14672750713245
886 14739237155986
887 14805949295035
888 14872887640584
889 14940052703401
890 15007444994830
891 15075065026791
892 15142913311780
893 15210990362869
894 15279296693706
895 15347832818515
896 15416599252096
897 15485596509825
898 15554825107654
899 15624285562111
900 15693978390300
901 15763904109901
902 15834063239170
903 15904456296939
904 15975083802616
905 16045946276185
906 16117044238206
907 16188378209815
908 16259948712724
909 16331756269221
910 16403801402170
911 16476084635011
912 16548606491760
913 16621367497009
914 16694368175926
915 16767609054255
916 16841090658316
917 16914813515005
918 16988778151794
919 17062985096731
920 17137434878440
921 17212128026121
922 17287065069550
923 17362246539079
924 17437672965636
925 17513344880725
926 17589262816426
927 17665427305395
928 17741838880864
929 17818498076641
930 17895405427110
931 17972561467231
932 18049966732540
933 18127621759149
934 18205527083746
935 18283683243595
936 18362090776536
937 18440750220985
938 18519662115934
939 18598827000951
940 18678245416180
941 18757917902341
942 18837845000730
943 18918027253219
944 18998465202256
945 19079159390865
946 19160110362646
947 19241318661775
948 19322784833004
949 19404509421661
950 19486492973650
951 19568736035451
952 19651239154120
953 19734002877289
954 19817027753166
955 19900314330535
956 19983863158756
957 20067674787765
958 20151749768074
959 20236088650771
960 20320691987520
961 20405560330561
962 20490694232710
963 20576094247359
964 20661760928476
965 20747694830605
966 20833896508866
967 20920366518955
968 21007105417144
969 21094113760281
970 21181392105790
971 21268941011671
972 21356761036500
973 21444852739429
974 21533216680186
975 21621853419075
976 21710763516976
977 21799947535345
978 21889406036214
979 21979139582191
980 22069148736460
981 22159434062781
982 22249996125490
983 22340835489499
984 22431952720296
985 22523348383945
986 22615023047086
987 22706977276935
988 22799211641284
989 22891726708501
990 22984523047530
991 23077601227891
992 23170961819680
993 23264605393569
994 23358532520806
995 23452743773215
996 23547239723196
997 23642020943725
998 23737088008354
999 23832441491211
1000 23928081967000