4 1
5 0
6 1
7 1
8 3
9 3
10 5
11 6
12 11
13 13
14 20
15 24
16 37
17 45
18 64
19 80
20 110
21 137
22 184
23 229
24 303
25 375
26 486
27 602
28 772
29 951
30 1202
31 1478
32 1853
33 2267
34 2817
35 3432
36 4236
37 5142
38 6300
39 7620
40 9284
41 11185
42 13553
43 16273
44 19625
45 23478
46 28187
47 33613
48 40192
49 47778
50 56904
51 67443
52 80051
53 94597
54 111905
55 131877
56 155527
57 182798
58 214948
59 251999
60 295508
61 345605
62 404215
63 471642
64 550277
65 640624
66 745673
67 866252
68 1006051
69 1166321
70 1351654
71 1563879
72 1808707
73 2088705
74 2410974
75 2779097
76 3201912
77 3684267
78 4237169
79 4867181
80 5587957
81 6408244
82 7345032
83 8409862
84 9623867
85 11002140
86 12570937
87 14349939
88 16371739
89 18661747
90 21260438
91 24200555
92 27532252
93 31297435
94 35558293
95 40368242
96 45804316
97 51934318
98 58853524
99 66647796
100 75434888
101 85323008
102 96457613
103 108974766
104 123053859
105 138865414
106 156630556
107 176562426
108 198933244
109 224008729
110 252123589
111 283608422
112 318874359
113 358331510
114 402484410
115 451840912
116 507019308
117 568647097
118 637481228
119 714295519
120 800015595
121 895593874
122 1002160882
123 1120886859
124 1253151097
125 1400388652
126 1564280520
127 1746583842
128 1949344696
129 2174711006
130 2425170638
131 2703345083
132 3012255984
133 3355097875
134 3735536522
135 4157459305
136 4625308610
137 5143807786
138 5718334574
139 6354620570
140 7059168436
141 7838923748
142 8701741300
143 9656026686
144 10711257941
145 11877594647
146 13166461374
147 14590122849
148 16162335745
149 17897887716
150 19813326863
151 21926462302
152 24257179427
153 26826901223
154 29659500045
155 32780717060
156 36219182719
157 40005792808
158 44174850508
159 48763399059
160 53812499139
161 59366517110
162 65474556126
163 72189699275
164 79570612049
165 87680742491
166 96590116638
167 106374496186
168 117117391630
169 128909180361
170 141849364343
171 156045654221
172 171616501190
173 188690152306
174 207407494228
175 227921086844
176 250398356790
177 275020622148
178 301986681028
179 331511839809
180 363831948873
181 399202451653
182 437902925330
183 480236174074
184 526533339654
185 577153064581
186 632487251377
187 692960327580
188 759035736822
189 831215349269
190 910046782341
191 996123003522
192 1090090593631
193 1192649600491
194 1304562871497
195 1426656231045
196 1559829025284
197 1705054706406
198 1863392759095
199 2035989791329
200 2224093027425
201 2429052028998
202 2652333970178
203 2895526127354
204 3160353184972
205 3448680660398
206 3762534520206
207 4104105740327
208 4475772550519
209 4880106359710
210 5319897000386
211 5798160288805
212 6318166683139
213 6883450801495
214 7497843972678
215 8165486079397
216 8890862551109
217 9678818965134
218 10534603104080
219 11463882825081
220 12472793890895
221 13567961692537
222 14756555676476
223 16046315600957
224 17445613484801
225 18963485196805
226 20609700990141
227 22394803338857
228 24330187276812
229 26428145545118
230 28701960120771
231 31165955912573
232 33835605059504
233 36727590594022
234 39859925330749
235 43252027135995
236 46924854465455
237 50900995144096
238 55204820911599
239 59862591890617
240 64902632837470
241 70355455812406
242 76253961204619
243 82633581506235
244 89532510611240
245 96991872014726
246 105055980397150
247 113772538066884
248 123192933378415
249 133372469819997
250 144370706463078
251 156251724721887
252 169084516766710
253 182943295726125
254 197907938812405
255 214064347591693
256 231504953505733
257 250329135777953
258 270643798109086
259 292563852883035
260 316212878997641
261 341723682301551
262 369239045914913
263 398912378219035
264 430908568601154
265 465404735941222
266 502591204477070
267 542672367587309
268 585867800487709
269 632413256174937
270 682561933988536
271 736585626954113
272 794776167805529
273 857446749689757
274 924933574208743
275 997597370473068
276 1075825273078060
277 1160032567979459
278 1250664832080798
279 1348199938371000
280 1453150493083011
281 1566066136972088
282 1687536320904815
283 1818192945226546
284 1958713520088384
285 2109824190632234
286 2272303334605431
287 2446985027552400
288 2634763137325950
289 2836595290857049
290 3053507533103353
291 3286598865337296
292 3537046545070173
293 3806111275192288
294 4095143231641959
295 4405587993406416
296 4738993396136657
297 5097016305133444
298 5481430406122108
299 5894133936928595
300 6337158541322520
301 6812678090514681
302 7323018742495720
303 7870669001930729
304 8458291146103276
305 9088732691380443
306 9765039368022295
307 10490468183577606
308 11268502152512771
309 12102865171989438
310 12997538739110358
311 13956778882681370
312 14985135131132117
313 16087469775716565
314 17268979386172422
315 18535216716746014
316 19892115105011827
317 21346013372470357
318 22903683485242702
319 24572358846543914
320 26359765646506148
321 28274154995197028
322 30324338443620184
323 32519724463588370
324 34870358683611295
325 37386965286943263
326 40080992575301560
327 42964659929589184
328 46051009392315598
329 49353958917639176
330 52888360751093443
331 56670061788062815
332 60715969627764418
333 65044120963302779
334 69673756297565845
335 74625397404670974
336 79920931819796553
337 85583700543076103
338 91638593554882585
339 98112149080675941
340 105032661539962159
341 112430293855929438
342 120337199422338292
343 128787649127497846
344 137818169120539438
345 147467684427797242
346 157777674521376641
347 168792335639615262
348 180558756409231570
349 193127101243764700
350 206550808548847585
351 220886797866584462
352 236195693505514242
353 252542058428218551
354 269994646497373070
355 288626666473111330
356 308516066458054450
357 329745831784749567
358 352404305681359498
359 376585525292556033
360 402389583078894457
361 429923005733305850
362 459299161376930857
363 490638686714143701
364 524069945703030261
365 559729510941492295
366 597762680179333682
367 638324018655037918
368 681577940586357010
369 727699319990763743
370 776874145152849762
371 829300206370557851
372 885187832360811149
373 944760664390340188
374 1008256484657128527
375 1075928087401128351
376 1148044210501894150
377 1224890515433956562
378 1306770634665053387
379 1394007273739417670
380 1486943388561561677
381 1585943424475215273
382 1691394639193726495
383 1803708495511001955
384 1923322147510843858
385 2050700005521050793
386 2186335405322116532
387 2330752366159802268
388 2484507465003953987
389 2648191810893678495
390 2822433148897131143
391 3007898076806701707
392 3205294406349834932
393 3415373651311416073
394 3638933676779202993
395 3876821491181541081
396 4129936217955899976
397 4399232227792986341
398 4685722471134279972
399 4990481991152181071
400 5314651659959522858
401 5659442117577480710
402 6026137959728320349
403 6416102153303677778
404 6830780729166910449
405 7271707730494003987
406 7740510470198751666
407 8238915075042304467
408 8768752374182596635
409 9331964109211854120
410 9930609527998179070
411 10566872338894661296
412 11243068092573203077
413 11961651967643931092
414 12725227032674901805
415 13536552960468334020
416 14398555273018971548
417 15314335092825639158
418 16287179485285217579
419 17320572367796104529
420 18418206077143284732
421 19583993570913196182
422 20822081361941194747
423 22136863161856122964
424 23532994340795444180
425 25015407179898848068
426 26589327032425102656
427 28260289370904807025
428 30034157845709839026
429 31917143333561260465
430 33915824111725935632
431 36037167137882058679
432 38288550582686474462
433 40677787596881387667
434 43213151472253446742
435 45903402180598649811
436 48757814463374877573
437 51786207459033905827
438 54998976055276663834
439 58407123956654206972
440 62022298670624800694
441 65856828406595769508
442 69923761108352400146
443 74236905619273262207
444 78810875219589108578
445 83661133540818208636
446 88804043117200361368
447 94256916585973144405
448 100038070818747989966
449 106166884003641892304
450 112663855984909071473
451 119550671888778090400
452 126850269368971974764
453 134586909511061985738
454 142786251758324260981
455 151475432910261280894
456 160683150588346830208
457 170439751233922372443
458 180777323067648679795
459 191729794091176697035
460 203333035598523684138
461 215624971295759985482
462 228645692538127447003
463 242437579803599392282
464 257045430957532946795
465 272516596450585847306
466 288901122054345854538
467 306251899303085151306
468 324624824300570292360
469 344078965090011763902
470 364676738305703858367
471 386484095337941002905
472 409570718795013773248
473 434010229531639986150
474 459880405099070713220
475 487263409928742693181
476 516246038182937640576
477 546919969632123981003
478 579382039578101568035
479 613734523236307885584
480 650085435690235584103
481 688548847891533023988
482 729245219921530341537
483 772301752055235171172
484 817852754956165664092
485 866040039618596074104
486 917013328509004801797
487 970930688607768383513
488 1027958987938162559441
489 1088274376378101867050
490 1152062792489949787414
491 1219520497269213981508
492 1290854636710005090180
493 1366283834205635879418
494 1446038814860452893918
495 1530363062862336550841
496 1619513514187366824368
497 1713761285932092263198
498 1813392444759181538873
499 1918708815914428199772
500 2030028835535888303980
501 2147688447893952169927
502 2272042050540864760209
503 2403463489209559404789
504 2542347105723016486313
505 2689108840977436982388
506 2844187396570535628343
507 3008045457386389650064
508 3181170979048303040155
509 3364078542826577635418
510 3557310782285809378074
511 3761439884564208292527
512 3977069170978938094760
513 4204834760188881072699
514 4445407319057942612294
515 4699493904825958022440
516 4967839904223057586119
517 5251231073550751021988
518 5550495685906196527288
519 5866506790033843730861
520 6200184587574042458189
521 6552498933703058238254
522 6924471968584849623537
523 7317180885193665625970
524 7731760841641817764143
525 8169408024196234102022
526 8631382869901517795010
527 9119013455683698513812
528 9633699063711882271256
529 10176913930655298587027
530 10750211191555927765115
531 11355227026797626770333
532 11993685023926490073243
533 12667400763734983184989
534 13378286643499597554950
535 14128356947813258127680
536 14919733181147421138420
537 15754649673720633709680
538 16635459476174498050375
539 17564640555886905753999
540 18544802311921992920611
541 19578692422829074001653
542 20669204045933799289501
543 21819383383858399298500
544 23032437638717337329041
545 24311743371406203088221
546 25660855288407887176369
547 27083515475386714510488
548 28583663102163739881607
549 30165444620385651318385
550 31833224480859482680470
551 33591596394114939386510
552 35445395163775543820630
553 37399709118777812829975
554 39459893176880747792894
555 41631582568232769076203
556 43920707254575660805454
557 46333507075855684118566
558 48876547663261385589962
559 51556737153763331325158
560 54381343748946870526354
561 57358014156849835820428
562 60494792963731137748584
563 63800142978482793210774
564 67282966601144163109361
565 70952628262630952809817
566 74818977992106457512404
567 78892376163945838161116
568 83183719486166985026373
569 87704468287597704632891
570 92466675171621649579755
571 97483015099618907405658
572 102766816978484967955647
573 108332096821768362756230
574 114193592565978718527637
575 120366800618663839153067
576 126868014227661719163780
577 133714363755879361387958
578 140923858959609532229610
579 148515433363252310426125
580 156508990837879837946361
581 164925454485860871745176
582 173786817949310508312395
583 183116199254846051378543
584 192937897323725879355599
585 203277451271118699038765
586 214161702635968746494252
587 225618860677568333067718
588 237678570893870586361915
589 250371986911219852027957
590 263731845915389197662343
591 277792547788484871160865
592 292590238137873998519027
593 308162895398018939886125
594 324550422209183881592467
595 341794741271798272097286
596 359939895899938779668985
597 379032155492342372622261
598 399120126165752752400763
599 420254866790530489024662
600 442490010696686330756649
601 465881893313853552219833
602 490489686038920766957882
603 516375536620688875124931
604 543604716383245507967647
605 572245774605743157677614
606 602370700410880445113587
607 634055092510801894479165
608 667378337196200566138349
609 702423794951328129003056
610 739278996117327432414856
611 778035846023817970384682
612 818790840051217300315896
613 861645289084493117672761
614 906705555864652355466539
615 954083302743294434586997
616 1003895751394460601275441
617 1056265955037966705343688
618 1111323083780857801431864
619 1169202723684652432714389
620 1230047190222315259005546
621 1294005856791155020324728
622 1361235499008231003534664
623 1431900655518510006683197
624 1506174006110837016663702
625 1584236767942032141534485
626 1666279110739028307154022
627 1752500591856014365368794
628 1843110612138304750554209
629 1938328893553740313257637
630 2038385979632740348752137
631 2143523759769499426129412
632 2253996018523134425358353
633 2370069011071534329041103
634 2492022066063446784335273
635 2620148217131168795560472
636 2754754864425972259837683
637 2896164467558459056500093
638 3044715271433340025465292
639 3200762066491806274280148
640 3364676984990097088444789
641 3536850334970570623887316
642 3717691473705805141483742
643 3907629722428447560796433
644 4107115324293236699600744
645 4316620447554809751517277
646 4536640236088861451671488
647 4767693909426953711975420
648 5010325914630309199905205
649 5265107132376807124293070
650 5532636139802402898268799
651 5813540532693903508945813
652 6108478309809968455647791
653 6418139322170475571890687
654 6743246790348311102667987
655 7084558892869276807959609
656 7442870429034843555238145
657 7819014559563360338432661
658 8213864628670709905676325
659 8628336071302494304759024
660 9063388409472892936960203
661 9520027341767698925493160
662 9999306930331218525593072
663 10502331889771511521655255
664 11030259982701311949038365
665 11584304526760460077183038
666 12165737018270913958271646
667 12775889877818986228369086
668 13416159323388900302461215
669 14088008376831940727130844
670 14792970009811120333138070
671 15532650435539729738920230
672 16308732553016136896653374
673 17122979550655722540779471
674 17977238676635529045259134
675 18873445183487774591649224
676 19813626454926296228193303
677 20799906323134779811688028
678 21834509585229509141582090
679 22919766727880743482143924
680 24058118869599642062126497
681 25252122930498192605929405
682 26504457039894566633467888
683 27817926192468839037884635
684 29195468164284622761279719
685 30640159700359731189154798
686 32155222986129025836726156
687 33744032415548565350060906
688 35410121669303749327091985
689 37157191117032158396287921
690 38989115558243346795366623
691 40909952317111883239703437
692 42923949707154285425637018
693 45035555882344905318051462
694 47249428092128187527540234
695 49570442358384237354202052
696 52003703593380674419549634
697 54554556178403517728295874
698 57228595023815694340360430
699 60031677132017402738865482
700 62969933685924861563971143
701 66049782686381595435804857
702 69277942163152365572665384
703 72661443985026111761185606
704 76207648295891691068444232
705 79924258604612340810183217
706 83819337557972134559169551
707 87901323427023611244662186
708 92179047338732188939581861
709 96661751285971236068218835
710 101359106950617129534139131
711 106281235375763576031865377
712 111438727524909720223366026
713 116842665767368351070179126
714 122504646331127221363271838
715 128436802765921168017364693
716 134651830461423521446428744
717 141163012267134859177374384
718 147984245262875752658565644
719 155130068730617674061273737
720 162615693380907456559708439
721 170457031889140362747777866
722 178670730799666753742439869
723 187274203857904581069380796
724 196285666833585991378450571
725 205724173900657893902185730
726 215609655642557409799747706
727 225962958754197223890697471
728 236805887515462373407301938
729 248161247113876434824491368
730 260052888897849174167617504
731 272505757645037965936944485
732 285545940934420968893605522
733 299200720714087435602640479
734 313498627161153778198973514
735 328469494933933889459890291
736 344144521921261168995226888
737 360556330597919579282842070
738 377739032100306192706411411
739 395728293140877426601700058
740 414561405885525496146749840
741 434277360922863624374008958
742 454916923460457825947689559
743 476522712888312539733380378
744 499139285856480318751752907
745 522813223019410860956614594
746 547593219606763172306050869
747 573530179986666754804744907
748 600677316395117181768556645
749 629090252012015471711805677
750 658827128572700244717932964
751 689948718711256366074211093
752 722518543240916660120608181
753 756602993584971512459454652
754 792271459581384958128655981
755 829596462893134904654878755
756 868653796266892168340910891
757 909522668892254998394435075
758 952285858125233532556387399
759 997029867850130924674653915
760 1043845093766399442306872131
761 1092825995898425442755286207
762 1144071278639661544941311107
763 1197684078654902373431277610
764 1253772160979083077322385436
765 1312448123664446096117273287
766 1373829611343715485631852206
767 1438039538091565529530282184
768 1505206319983775418734066738
769 1575464117769391026773576224
770 1648953090089739503885551444
771 1725819657695462576287637685
772 1806216779132796079021626145
773 1890304238389152497369168306
774 1978248945009788798729656942
775 2070225247217808152692624219
776 2166415258593270812695986518
777 2267009198889431427990769431
778 2372205749589596427677548062
779 2482212424832262892872607447
780 2597245958359787065680100672
781 2717532707172086719125909440
782 2843309072596752479161780044
783 2974821939515463522938780079
784 3112329134518946022175219861
785 3256099903793687771846967298
786 3406415411578640721989119245
787 3563569260063779121003847572
788 3727868031640294388533838190
789 3899631854448727900149334709
790 4079194992212389079458491314
791 4266906459383051831080057068
792 4463130662670358346754384994
793 4668248070069391854244626029
794 4882655908548983503960156225
795 5106768891610020778529758324
796 5341019977975096432908611736
797 5585861162721514722777799670
798 5841764302226036005235149525
799 6109221974344725027945137571
800 6388748375312276242593398549
801 6680880254904838143198335911
802 6986177891476389713923841746
803 7305226108543422316805727099
804 7638635334664144519395705725
805 7987042708428597875241930282
806 8351113230453412040609167937
807 8731540964351021143319195371
808 9129050288726858735806104100
809 9544397202340554760296246678
810 9978370684657725837159463199
811 10431794114108398119739717509
812 10905526746466101373893045496
813 11400465255858634885755929051
814 11917545341027540762611939992
815 12457743399558414650171363527
816 13022078272918906932325067181
817 13611613065255162961528096046
818 14227457039021566893747222656
819 14870767590642072709791388229
820 15542752309535676427426963814
821 16244671123972306825560888759
822 16977838537370659221918970645
823 17743625958794368158843796222
824 18543464131560027077644334168
825 19378845664027493953192426659
826 20251327666812858301439999133
827 21162534500834420293798654550
828 22114160640785829184316360848
829 23107973658814611922007242284
830 24145817333383097782512019991
831 25229614888488086093807921179
832 26361372368630565188059668730
833 27543182155142630801826151515
834 28777226629711203067851875394
835 30065781991171820757075993347
836 31411222231897139699882675168
837 32816023280357728956274091197
838 34282767316704523266074048128
839 35814147268496107326493560014
840 37412971493987829070209161133
841 39082168660696094386211298132
842 40824792827268844070257091907
843 42644028737013929604769142418
844 44543197331780489743837640650
845 46525761495235473478959269950
846 48595332034948638909069327804
847 50755673913074852470166267352
848 53010712735823720080100501754
849 55364541512312820097868376521
850 57821427693834438586868791397
851 60385820505005162914108289748
852 63062358578736333597383241822
853 65855877907438696729460464893
854 68771420123381050493800956643
855 71814241121636789424743836653
856 74989820039599522670335520054
857 78303868607604928844462408943
858 81762340885787355403818281315
859 85371443402900886804602834506
860 89137645713473530736114932514
861 93067691390313236249657596439
862 97168609470074744735665701930
863 101447726370299090579253567402
864 105912678297083296748810722324
865 110571424163297588004024350827
866 115432259038073013094961338670
867 120503828149103647353918513155
868 125795141460177699497046353728
869 131315588847239526582345304152
870 137074955897224411805130830865
871 143083440354867321562011788054
872 149351669243701921620166375500
873 155890716688502870814046035496
874 162712122467520631702865269494
875 169827911323978293878439117462
876 177250613067483692921256544622
877 184993283497220502736624386309
878 193069526180060240744366392522
879 201493515118044796359076917942
880 210280018341069275345939257102
881 219444422462007594299071445504
882 229002758233013387169392917676
883 238971727143254692099374364473
884 249368729099949608749543876582
885 260211891236218226810510224864
886 271520097891002762669975128312
887 283313021808087790456281487287
888 295611156603127047213193878737
889 308435850549505462829159713285
890 321809341735888437150259313543
891 335754794650385967664105867027
892 350296338248443039808246307864
893 365459105563808738681854225861
894 381269274924293346589438368206
895 397754112836442192464423142844
896 414942018605798352284325567012
897 432862570762038249927504636486
898 451546575361008643076775334628
899 471026116238512952956097148138
900 491334607293656132373037043933
901 512506846882600503337886468059
902 534579074406779939424932247617
903 557589029182904258436427439261
904 581576011685532551829570896757
905 606580947256538759729712835027
906 632646452379511186962107825438
907 659816903620952617942612148524
908 688138509344158715370712480681
909 717659384305779577899869009359
910 748429627249395734531844939553
911 780501401614892797226791630898
912 813929019487085249084546043236
913 848769028911843873351951510738
914 885080304713013790142392032937
915 922924142948592451942941337991
916 962364359150063985142277253838
917 1003467390494376365638062624031
918 1046302402063900064514828526130
919 1090941397355736223445329098709
920 1137459333208052548439403078707
921 1185934239317627878517233479426
922 1236447342529589872857545949526
923 1289083196087342990910332301081
924 1343929814038018858366974020483
925 1401078810996343217244395468411
926 1460625547477720980826855304839
927 1522669281019494808218690199167
928 1587313323317856429511184534098
929 1654665203616681277828788449940
930 1724836838593744735200321554699
931 1797944708999256169018102982973
932 1874110043311549663886102191094
933 1953459008684987612305105197319
934 2036122909475805948075566444691
935 2122238393642643308528789392603
936 2211947667329998001490957949571
937 2305398717954727564082822285096
938 2402745546128099809711273398475
939 2504148406758698378130015786172
940 2609774059694840789540308473496
941 2719796030278955106962672406896
942 2834394880200750697513553166993
943 2953758489050876799283025025515
944 3078082346992265461986731342357
945 3207569858982365636109092698218
946 3342432660996176561401835550507
947 3482890948717238858216185335372
948 3629173819181733064351901349238
949 3781519625879420352043193145955
950 3940176347834539795684222191927
951 4105401973209798116609187907869
952 4277464897997461494546021395435
953 4456644340383126640218710491354
954 4643230771390229690580168445920
955 4837526362436582856960889817646
956 5039845450458440038545213250615
957 5250515021282614300752697433195
958 5469875211953242694093969297164
959 5698279832746741943407883295023
960 5936096909636573631866950490888
961 6183709247998458171472323849789
962 6441515018376906263307451218978
963 6709928365165187027947673690075
964 6989380039083398868766579723568
965 7280318054372958374498962303212
966 7583208371660862267614063459714
967 7898535607483306999627899421766
968 8226803771495971552109041798788
969 8568537032437274090996032111936
970 8924280513951517833629798252237
971 9294601121420831772062536924405
972 9680088400998517950815830693984
973 10081355432081617806777660891764
974 10499039754507551266898684787480
975 10933804331808335742574410308676
976 11386338551906519663795386135865
977 11857359266689331392294245505879
978 12347611871952028025363311526720
979 12857871429257787003057484884251
980 13388943831320113162670322585470
981 13941667012574384692724009161597
982 14516912206668248625935637448328
983 15115585252665842199373447161480
984 15738627951828695532069987126188
985 16387019476906398013372960531731
986 17061777835943141100800298328655
987 17763961392681810445978695546124
988 18494670445725867584797521578055
989 19255048868700554469723308266767
990 20046285813739472801331944596333
991 20869617480710045056884187109127
992 21726328954682279105435575452488
993 22617756114239335901268568185517
994 23545287613326188834572717597496
995 24510366939433858339159521967255
996 25514494551021881545372119877036
997 26559230097190520432123368329043
998 27646194722727326012925936326121
999 28777073461769738749836616044864
1000 29953617723447048686318056096749