1 1
2 6
3 9
4 13
5 19
6 37
7 58
8 97
9 143
10 227
11 328
12 492
13 688
14 992
15 1364
16 1903
17 2551
18 3473
19 4586
20 6097
21 7911
22 10333
23 13226
24 16988
25 21454
26 27172
27 33938
28 42437
29 52423
30 64833
31 79354
32 97130
33 117824
34 142930
35 172018
36 206925
37 247179
38 295105
39 350154
40 415124
41 489414
42 576540
43 675794
44 791345
45 922483
46 1074325
47 1246034
48 1443675
49 1666409
50 1921549
51 2208184
52 2534870
53 2900714
54 3315970
55 3779668
56 4303685
57 4887189
58 5544215
59 6273874
60 7092385
61 7999055
62 9012833
63 10133110
64 11381593
65 12757967
66 14287467
67 15969932
68 17834062
69 19880242
70 22141526
71 24618572
72 27348872
73 30333812
74 33616232
75 37198092
76 41127678
77 45407930
78 50093798
79 55189020
80 60755196
81 66797520
82 73385628
83 80525820
84 88295958
85 96704202
86 105838062
87 115707372
88 126409512
89 137956692
90 150457992
91 163927788
92 178486950
93 194153058
94 211060830
95 229230636
96 248811405
97 269827473
98 292444095
99 316689378
100 342745323
101 370644933
102 400589595
103 432616998
104 466948185
105 503627091
106 542897355
107 584808708
108 629628010
109 677412538
110 728455398
111 782821248
112 840830155
113 902555863
114 968349085
115 1038292486
116 1112767975
117 1191869393
118 1276013915
119 1365306118
120 1460199444
121 1560811714
122 1667636828
123 1780805774
124 1900854043
125 2027928265
126 2162610527
127 2305063046
128 2455915462
129 2615348736
130 2784045550
131 2962205246
132 3150565067
133 3349346221
134 3559346167
135 3780808070
136 4014591308
137 4260964474
138 4520855508
139 4794558574
140 5083071695
141 5386718909
142 5706575563
143 6042995374
144 6397133223
145 6769377225
146 7160969257
147 7572332196
148 8004797372
149 8458827156
150 8935850976
151 9436371152
152 9961917485
153 10513037977
154 11091372175
155 11697513854
156 12333215415
157 12999122657
158 13697110495
159 14427877522
160 15193424597
161 15994509407
162 16833269815
163 17710523512
164 18628548620
165 19588230324
166 20591998940
167 21640807672
168 22737243280
169 23882335112
170 25078838672
171 26327860792
172 27632330380
173 28993439972
174 30414305820
175 31896207704
176 33442453720
177 35054420512
178 36735623000
179 38487535832
180 40313886428
181 42216257828
182 44198605388
183 46262622648
184 48412499088
185 50650049288
186 52979714192
187 55403431800
188 57925900572
189 60549194100
190 63278286924
191 66115390200
192 69065761977
193 72131764065
194 75318957147
195 78629856798
196 82070334393
197 85643072583
198 89354274753
199 93206794098
200 97207173969
201 101358453303
202 105667538163
203 110137656288
204 114776086008
205 119586260148
206 124575852732
207 129748506060
208 135112300167
209 140671103415
210 146433427785
211 152403372546
212 158589891885
213 164997334731
214 171635125065
215 178507865922
216 185625463180
217 192992794006
218 200620274580
219 208513062186
220 216682096321
221 225132834811
222 233876771725
223 242919671986
224 252273597250
225 261944642432
226 271945469930
227 282282510826
228 292969043385
229 304011859231
230 315424886621
231 327215285666
232 339397650820
233 351979535566
234 364976237900
235 378395713322
236 392253979645
237 406559422071
238 421328817745
239 436570989866
240 452303493587
241 468535619497
242 485285741413
243 502563627632
244 520388490578
245 538770606286
246 557730070062
247 577277676844
248 597434424917
249 618211661309
250 639631334023
251 661705353034
252 684456638877
253 707897699619
254 732052476397
255 756934088526
256 782567522033
257 808966543407
258 836157235683
259 864154026692
260 892984121018
261 922662647302
262 953217986578
263 984665982212
264 1017036219288
265 1050345297596
266 1084624062712
267 1119889887364
268 1156174906922
269 1193497309694
270 1231890581794
271 1271373744820
272 1311981665300
273 1353734244720
274 1396667794100
275 1440803112340
276 1486177988050
277 1532814166670
278 1580750980250
279 1630011141220
280 1680635560120
281 1732647966620
282 1786090920600
283 1840989190820
284 1897387022050
285 1955310276790
286 2014804959050
287 2075898046820
288 2138637342725
289 2203050997745
290 2269188689495
291 2337079766970
292 2406775824375
293 2478307467545
294 2551728289175
295 2627070178590
296 2704388769225
297 2783717297595
298 2865113523675
299 2948612057820
300 3034272833046
301 3122131900446
302 3212251454178
303 3304669016376
304 3399449091363
305 3496630740759
306 3596280873237
307 3698440122078
308 3803177850147
309 3910536336213
310 4020587495847
311 4133375285598
312 4248974228292
313 4367430035658
314 4488819938892
315 4613191441254
316 4740624539703
317 4871168608221
318 5004906517323
319 5141889550206
320 5282203509342
321 5425901672256
322 5573072885958
323 5723772461046
324 5878092352663
325 6036089993569
326 6197860562547
327 6363463657758
328 6532997748412
329 6706524689218
330 6884146362628
331 7065926925574
332 7251971741755
333 7442347367969
334 7637162777255
335 7836486972358
336 8040432609375
337 8249071239049
338 8462519331905
339 8680851037724
340 8904186718744
341 9132603228184
342 9366224959340
343 9605131522664
344 9849451421245
345 10099267134273
346 10354711419775
347 10615869680054
348 10882879013075
349 11155827860629
350 11434857809419
351 11720060400554
352 12011581798445
353 12309516762559
354 12614016192495
355 12925178129008
356 13243158297560
357 13568058146984
358 13900038392440
359 14239203954544
360 14585720635680
361 14939696960400
362 15301303986208
363 15670653911280
364 16047923150168
365 16433227709832
366 16826749539192
367 17228608527152
368 17638992260912
369 18058024654912
370 18485899118896
371 18922743666992
372 19368757642872
373 19824073309832
374 20288896134232
375 20763362709232
376 21247684740128
377 21742003302800
378 22246536540448
379 22761430096240
380 23286908669816
381 23823122633640
382 24370303450328
383 24928606307440
384 25498269557233
385 26079453370817
386 26672403201587
387 27277284297142
388 27894349344037
389 28523768838587
390 29165802923037
391 29820627439658
392 30488510121025
393 31169632337503
394 31864269642755
395 32572609033976
396 33294934029380
397 34031437442168
398 34782410991320
399 35548053412548
400 36328664774943
401 37124449930103
402 37935717545345
403 38762678699418
404 39605650810185
405 40464851387631
406 41340606857205
407 42233141273178
408 43142790230460
409 44069784539358
410 45014469227268
411 45977081982018
412 46957977431805
413 47957400358383
414 48975715266585
415 50013174158826
416 51070151588250
417 52146907005888
418 53243825298690
419 54361173495138
420 55499346997989
421 56658620649459
422 57839400660153
423 59041969823994
424 60266745348468
425 61514018220630
426 62784216950652
427 64077640862466
428 65394729961737
429 66735792163131
430 68101279284045
431 69491507976066
432 70906942072267
433 72347907224041
434 73814879603517
435 75308194017960
436 76828339190158
437 78375659351794
438 79950656114458
439 81553683296644
440 83185255614565
441 84845736755429
442 86535654889463
443 88255383737794
444 90005465152473
445 91786283180215
446 93598393712057
447 95442191296166
448 97318246098697
449 99226963467151
450 101168928215771
451 103144556674172
452 105154448545510
453 107199031453722
454 109278920375950
455 111394554416444
456 113546564080040
457 115735400274052
458 117961709424520
459 120225954439292
460 122528797928342
461 124870715129602
462 127252385247390
463 129674296054732
464 132137143618220
465 134641428590864
466 137187864324940
467 139776964562092
468 142409460222030
469 145085878491282
470 147806968289542
471 150573270469212
472 153385552241480
473 156244368488292
474 159150505162920
475 162104531406044
476 165107252210270
477 168159251355082
478 171261353336950
479 174414156807452
480 177618506078973
481 180875015067473
482 184184548375663
483 187547735430418
484 190965461447363
485 194438371764653
486 197967372704467
487 201553125771670
488 205196558723897
489 208898349650595
490 212659448253419
491 216480549466420
492 220362625280002
493 224306387903810
494 228312832136222
495 232382687736688
496 236516972667643
497 240716434678103
498 244982115434253
499 249314780958518
500 253715496983839
501 258185048264473
502 262724525155763
503 267334731432758
504 272016782453108
505 276771501485138
506 281600029455932
507 286503209431230
508 291482208299667
509 296537889406385
510 301671446190455
511 306883762590966
512 312176058997110
513 317549240443776
514 323004554876190
515 328542928745262
516 334165637969955
517 339873630934101
518 345668212148655
519 351550352266806
520 357521384822316
521 363582303264906
522 369734470792500
523 375978903999006
524 382316996185575
525 388749787638597
526 395278702421955
527 401904804868446
528 408629550262935
529 415454027549001
530 422379723905241
531 429407753257236
532 436539635149620
533 443776509065436
534 451119927612600
535 458571056214912
536 466131481024845
537 473802394004841
538 481585415568495
539 489481764607086
540 497493096297007
541 505620657073417
542 513866137606263
543 522230812283202
544 530716407784453
545 539324227077151
546 548056033608487
547 556913159346664
548 565897405032292
549 575010132285404
550 584253179917268
551 593627939628904
552 603136288850352
553 612779650032664
554 622559940017072
555 632478612453416
556 642537624158308
557 652738460662252
558 663083119577108
559 673573118776712
560 684210497242888
561 694996805899872
562 705934125941128
563 717024041812232
564 728268677515988
565 739669651745836
566 751229132171812
567 762948772226984
568 774830783863472
569 786876855994264
570 799089245740464
571 811469678001640
572 824020455694100
573 836743340470940
574 849640681953700
575 862714279064680
576 875966528781225
577 889399268082465
578 903014942228875
579 916815426794190
580 930803215990865
581 944980224789615
582 959348997312825
583 973911488481890
584 988670293010225
585 1003627406600455
586 1018785475539475
587 1034146536874640
588 1049713289173200
589 1065487811679740
590 1081472856242740
591 1097670544890940
592 1114083683480375
593 1130714437692215
594 1147565668423225
595 1164639585610930
596 1181939105932325
597 1199466484479315
598 1217224694768225
599 1235216037659890
600 1253443544276716
601 1271909562169766
602 1290617181146228
603 1309568796086746
604 1328767556270713
605 1348215904846499
606 1367917051678437
607 1387873488840098
608 1408088487582322
609 1428564589873408
610 1449305129490842
611 1470312698966618
612 1491590695435217
613 1513141762986503
614 1534969363272917
615 1557076192637394
616 1579465778102628
617 1602140869276766
618 1625105059749548
619 1648361153108826
620 1671912810378837
621 1695762890172351
622 1719915122173833
623 1744372420747866
624 1769138585136963
625 1794216586528809
626 1819610294971797
627 1845322739231328
628 1871357861082762
629 1897718747959638
630 1924409414649798
631 1951433008030044
632 1978793616838005
633 2006494448518989
634 2034539667076455
635 2062932541312698
636 2091677311466325
637 2120777308849419
638 2150236851275205
639 2180059333383294
640 2210249151555489
641 2240809764932079
642 2271745649842515
643 2303060330767284
644 2334758364994770
645 2366843343555438
646 2399319906107850
647 2432191711086324
648 2465463481564600
649 2499138944619724
650 2533222908176664
651 2567719168839924
652 2602632620456770
653 2637967130419654
654 2673727679975770
655 2709918208213348
656 2746543784869060
657 2783608422025904
658 2821117279421540
659 2859074443056964
660 2897485163795850
661 2936353602886870
662 2975685103857458
663 3015483904159700
664 3055755441137368
665 3096504029798572
666 3137735202884792
667 3179453353940372
668 3221664112276762
669 3264371951367582
670 3307582598711266
671 3351300608707412
672 3395531808250997
673 3440280834092977
674 3485553614169607
675 3531354868614122
676 3577690627642703
677 3624565696220545
678 3671986208534223
679 3719957055437710
680 3768484476347561
681 3817573449498635
682 3867230321265403
683 3917460158338060
684 3968269415347758
685 4019663248966182
686 4071648223838362
687 4124229587727912
688 4177414016623187
689 4231206850931607
690 4285614879789957
691 4340643537387278
692 4396299727360475
693 4452588979276573
694 4509518313117055
695 4567093354983566
696 4625321242594980
697 4684207700219738
698 4743759985189420
699 4803983921133718
700 4864886886422063
701 4926474805704773
702 4988755180314595
703 5051734037145838
704 5115419001943310
705 5179816205551296
706 5244933400093430
707 5310776821607398
708 5377354350087535
709 5444672328508553
710 5512738766734763
711 5581560115961038
712 5651144517447580
713 5721498532381778
714 5792630435471460
715 5864546899210166
716 5937256333304275
717 6010765523374633
718 6085083016221215
719 6160215711927158
720 6236172295982159
721 6312959784792329
722 6390587004666353
723 6469061089709964
724 6548391008682768
725 6628584015281120
726 6709649222899652
727 6791594006234136
728 6874427624972637
729 6958157576752401
730 7042793269784415
731 7128342326078886
732 7214814304075467
733 7302216952140861
734 7390559981208867
735 7479851267477850
736 7570100676119133
737 7661316213178239
738 7753507900386783
739 7846683875146464
740 7940854317520560
741 8036027498335824
742 8132213758357488
743 8229421503370464
744 8327661236662848
745 8426941501090080
746 8527272964871232
747 8628664309511136
748 8731126370020272
749 8834667968698896
750 8939300109816816
751 9045031758084192
752 9151874088920160
753 9259836211646592
754 9368929475349600
755 9479163135602784
756 9590548717101040
757 9703095623917072
758 9816815558911920
759 9931718076345312
760 10047815059227712
761 10165116214288672
762 10283633607307840
763 10403377099209952
764 10524358940558320
765 10646589148813904
766 10770080161995440
767 10894842155852512
768 11020887757927905
769 11148227304648577
770 11276873615794787
771 11406837190273382
772 11538131042214205
773 11670765835429987
774 11804754781178645
775 11940108710020634
776 12076841032486945
777 12214962748372527
778 12354487470314275
779 12495426369212072
780 12637793262010268
781 12781599493250368
782 12926859087060688
783 13073583563547188
784 13221787156269263
785 13371481563473143
786 13522681231093617
787 13675398037481290
788 13829646643228097
789 13985439109428215
790 14142790314331789
791 14301712503770890
792 14462220775994652
793 14624327564264430
794 14788048189875172
795 14953395275566578
796 15120384368067893
797 15289028282329623
798 15459342793632753
799 15631340911230938
800 15805038641381834
801 15980449190440768
802 16157588798818738
803 16336470872096978
804 16517111887326333
805 16699525452167003
806 16883728283534257
807 17069734193348650
808 17257560140926292
809 17447220145344230
810 17638731411617500
811 17832108168206386
812 18027367868399585
813 18224524953005571
814 18423597126946565
815 18624599045639602
816 18827548668279355
817 19032460867913321
818 19239353861418605
819 19448242741793176
820 19659145986287686
821 19872078910917626
822 20087060256793650
823 20304105565316276
824 20523233844187525
825 20744460863331637
826 20967805900592855
827 21193284956822066
828 21420917582803985
829 21650720013514271
830 21882712076281361
831 22116910242670806
832 22353334619407545
833 22592001917892431
834 22832932527929675
835 23076143403270252
836 23321655219692670
837 23569485176617986
838 23819654239548870
839 24072179856128556
840 24327083284548552
841 24584382224056212
842 24844098229336488
843 25106249253857772
844 25370857151820078
845 25637940134344266
846 25907520359032662
847 26179616297327484
848 26454250413299292
849 26731441442220624
850 27011212158587388
851 27293581564210524
852 27578572747149702
853 27866204979327834
854 28156501666382622
855 28449482353124556
856 28745170765967208
857 29043586726233972
858 29344754285214408
859 29648693543574732
860 29955428880724758
861 30264980680379442
862 30577373654241678
863 30892628471946252
864 31210770180808813
865 31531819740157201
866 31855802537152287
867 32182739823756354
868 32512657330357147
869 32845576605378709
870 33181523726757259
871 33520520542376710
872 33862593481152025
873 34207764694338035
874 34556060966225675
875 34907504754482020
876 35262123202282650
877 35619939077688010
878 35980979887217750
879 36345268712440160
880 36712833426792235
881 37083697429387735
882 37457888965132925
883 37835431753860710
884 38216354415570775
885 38600680994939745
886 38988440491691275
887 39379657278564710
888 39774360738713300
889 40172575577136610
890 40574331565112860
891 40979653743196910
892 41388572274564875
893 41801112539583385
894 42217305098117775
895 42637175673703270
896 43060755226720550
897 43488069828220160
898 43919150843971150
899 44354024695943710
900 44792723159206011
901 45235273011070461
902 45681706440844903
903 46132050584667366
904 46586338050066188
905 47044596336489114
906 47506858474725012
907 47973152331079118
908 48443511363637247
909 48917963810139853
910 49396543561094587
911 49879279229274638
912 50366205141733767
913 50857350290934473
914 51352749445671817
915 51852431981777284
916 52356433113984428
917 52864782606214436
918 53377516124437648
919 53894663824411696
920 54416261827598957
921 54942340686411321
922 55472936983189583
923 56008081670798686
924 56547811796804263
925 57092158719424049
926 57641159956908047
927 58194847276710898
928 58753258672189237
929 59316426325001183
930 59884388709176343
931 60457178424530264
932 61034834430248380
933 61617389749370884
934 62204883831896780
935 62797350128099288
936 63394828583368400
937 63997353080362664
938 64604964065596880
939 65217695858211864
940 65835589410503484
941 66458679483316724
942 67087007540572940
943 67720608788990904
944 68359525208836920
945 69003792458029728
946 69653453039119800
947 70308543065452344
948 70969105566679500
949 71635177116987444
950 72306801279148284
951 72984015092507544
952 73666862657856720
953 74355381485187624
954 75049616219443920
955 75749604845657688
956 76455392557890060
957 77167017821808324
958 77884526386822140
959 78607957203687384
960 79337356582229145
961 80072763963978465
962 80814226225489083
963 81561783303615870
964 82315482646793193
965 83075364692961687
966 83841477468868017
967 84613861918165842
968 85392566651134737
969 86177633123015127
970 86969110534153011
971 87767040856064832
972 88571473884488872
973 89382452113186372
974 90200025939906732
975 91024238385444012
976 91855140454972903
977 92692775702367415
978 93537195746968873
979 94388444680600930
980 95246574742257181
981 96111630567873755
982 96983665022943353
983 97862723292448930
984 98748858873976908
985 99642117507818422
986 100542553330589012
987 101450212642924682
988 102365150226156337
989 103287412947607627
990 104217056240386877
991 105154127543626898
992 106098682947974050
993 107050770470832768
994 108010446867558730
995 108977760739016906
996 109952769511145705
997 110935522374835183
998 111926077433869645
999 112924484474459138
1000 113930802284202308