6 1
7 0
8 1
9 1
10 2
11 2
12 5
13 5
14 8
15 10
16 15
17 18
18 27
19 32
20 45
21 56
22 75
23 92
24 123
25 150
26 195
27 240
28 306
29 374
30 473
31 575
32 718
33 873
34 1078
35 1304
36 1602
37 1928
38 2349
39 2821
40 3414
41 4083
42 4917
43 5857
44 7016
45 8334
46 9934
47 11758
48 13963
49 16472
50 19480
51 22918
52 27003
53 31673
54 37200
55 43509
56 50938
57 59428
58 69365
59 80717
60 93964
61 109073
62 126635
63 146667
64 169858
65 196285
66 226800
67 261522
68 301501
69 346963
70 399147
71 458425
72 526324
73 603342
74 691356
75 791104
76 904827
77 1033558
78 1180055
79 1345669
80 1533783
81 1746229
82 1987072
83 2258757
84 2566271
85 2912736
86 3304258
87 3744915
88 4242083
89 4801022
90 5430758
91 6137927
92 6933557
93 7826106
94 8828915
95 9952700
96 11213746
97 12625410
98 14207539
99 15976907
100 17957532
101 20170359
102 22644615
103 25406209
104 28490662
105 31930111
106 35767506
107 40042581
108 44807446
109 50110874
110 56016004
111 62582820
112 69887529
113 78003675
114 87023422
115 97036505
116 108154252
117 120486193
118 134166403
119 149328293
120 166133494
121 184743872
122 205354041
123 228160412
124 253396762
125 281300927
126 312153828
127 346242648
128 383904581
129 425486232
130 471391541
131 522038162
132 577909961
133 639508998
134 707414255
135 782228911
136 864644613
137 955384920
138 1055275788
139 1165183547
140 1286093510
141 1419042148
142 1565203180
143 1725815025
144 1902275128
145 2096060742
146 2308834015
147 2542355713
148 2798600310
149 3079663933
150 3387890604
151 3725772197
152 4096088778
153 4501800172
154 4946199813
155 5432799510
156 5965498201
157 6548457343
158 7186288459
159 7883918765
160 8646796864
161 9480750605
162 10392212997
163 11388069445
164 12475908537
165 13663858356
166 14960861946
167 16376505217
168 17921319733
169 19606599061
170 21444734973
171 23449022205
172 25634028090
173 28015389010
174 30610217322
175 33436886194
176 36515481397
177 39867574860
178 43516722350
179 47488230102
180 51809703433
181 56510803209
182 61623855384
183 67183598452
184 73227855852
185 79797280245
186 86936096205
187 94691838462
188 103116177599
189 112264654634
190 122197593821
191 132979841688
192 144681776928
193 157379052042
194 171153717388
195 186093969860
196 202295397783
197 219860747906
198 238901305680
199 259536680606
200 281896344191
201 306119441340
202 332356497344
203 360769271364
204 391532652554
205 424834558977
206 460878053320
207 499881299942
208 542079917682
209 587727017897
210 637095823412
211 690479796500
212 748195564727
213 810583159266
214 878009275200
215 950867653072
216 1029582714547
217 1114610104846
218 1206440760205
219 1305601643149
220 1412660282955
221 1528225751378
222 1652953735028
223 1787547782933
224 1932764987999
225 2089417555620
226 2258379156774
227 2440586886582
228 2637048372626
229 2848844175563
230 3077135760461
231 3323168414414
232 3588280172942
233 3873905354501
234 4181584562136
235 4512968918264
236 4869831291308
237 5254071343264
238 5667728117768
239 6112986045206
240 6592189063160
241 7107847708827
242 7662654982415
243 8259494694559
244 8901459271254
245 9591859565695
246 10334244850047
247 11132414289602
248 11990439416409
249 12912677513344
250 13903796859374
251 14968792326220
252 16113013744265
253 17342184009247
254 18662430985163
255 20080308484163
256 21602832124801
257 23237503621160
258 24992351095268
259 26875957117029
260 28897504056530
261 31066806404218
262 33394361766805
263 35891388094688
264 38569881030183
265 41442656691318
266 44523416199848
267 47826794788793
268 51368434375174
269 55165039889919
270 59234460903782
271 63595756126475
272 68269285251058
273 73276782729010
274 78641461070802
275 84388095181419
276 90543138546012
277 97134819496945
278 104193271928454
279 111750645083868
280 119841250560650
281 128501687448528
282 137771007648826
283 147690858337383
284 158305667910990
285 169662808045706
286 181812802773012
287 194809512734817
288 208710370246189
289 223576588573131
290 239473426235868
291 256470424542265
292 274641704671593
293 294066237149100
294 314828175738027
295 337017162882670
296 360728704975496
297 386064518353698
298 413132950939003
299 442049373993997
300 472936655795563
301 505925604865365
302 541155502080067
303 578774601856516
304 618940729728349
305 661821848819274
306 707596730829780
307 756455595874281
308 808600865834166
309 864247886687427
310 923625774094400
311 986978228520891
312 1054564484171544
313 1126660228277794
314 1203558665887397
315 1285571556135633
316 1373030406695886
317 1466287641462957
318 1565717940187608
319 1671719553528888
320 1784715805300766
321 1905156572838666
322 2033519971129712
323 2170314018650743
324 2316078525003701
325 2471386964544557
326 2636848591763663
327 2813110547754961
328 3000860230169277
329 3200827660608702
330 3413788139207565
331 3640564904076720
332 3882032104146639
333 4139117785530561
334 4412807219892228
335 4704146256758254
336 5014245049084517
337 5344281814795212
338 5695507006128284
339 6069247528808514
340 6466911406794226
341 6889992513189942
342 7340075788057524
343 7818842541078737
344 8328076286793222
345 8869668686038917
346 9445626069973737
347 10058076095113353
348 10709275035736583
349 11401615235512392
350 12137633257043047
351 12920018222659832
352 13751620919501497
353 14635463132695372
354 15574747815621574
355 16572869529962792
356 17633425803275086
357 18760228803465752
358 19957318019061880
359 21228973310175834
360 22579729062178212
361 24014388770687970
362 25538040836340520
363 27156074859145292
364 28874199260217768
365 30698459480578873
366 32635257636556818
367 34691372839296034
368 36873983113604966
369 39190688078646311
370 41649533384858278
371 44259036023104890
372 47028211562573683
373 49966602384598300
374 53084308035748260
375 56392016715381029
376 59901039091993538
377 63623343409914714
378 67571593155322111
379 71759186186879113
380 76200296680218687
381 80909918731822107
382 85903913056799241
383 91199055564521730
384 96813089336380021
385 102764778725178204
386 109073967196893105
387 115761637566002717
388 122849976347665985
389 130362440807667823
390 138323830541484990
391 146760362090000407
392 155699748539312634
393 165171282534585319
394 175205924778876499
395 185836396367215134
396 197097277157157897
397 209025108443132819
398 221658502275736806
399 235038255605820761
400 249207471743470520
401 264211687222140629
402 280099006715385034
403 296920244003443354
404 314729071806085992
405 333582178381259377
406 353539433885885856
407 374664064298615312
408 397022836091220731
409 420686249345280021
410 445728742705240449
411 472228907756521320
412 500269716437605253
413 529938758965051788
414 561328496111113862
415 594536523199924940
416 629665849909747053
417 666825193129567131
418 706129287221856092
419 747699208820873641
420 791662720798658430
421 838154632406416098
422 887317180524582674
423 939300428903269260
424 994262690647837287
425 1052370970705002073
426 1113801433945618507
427 1178739895471303792
428 1247382339107914479
429 1319935460581293682
430 1396617241730292573
431 1477657552121840889
432 1563298784839941933
433 1653796522682227934
434 1749420241984078052
435 1850454050170702693
436 1957197464736459407
437 2069966229621829635
438 2189093177197735419
439 2314929131699314589
440 2447843862867764261
441 2588227085514257639
442 2736489514352184479
443 2893063969689965124
444 3058406543957407638
445 3232997824541048244
446 3417344183575804601
447 3611979130055164500
448 3817464735629876737
449 4034393129354992862
450 4263388073527010810
451 4505106615778219304
452 4760240830400909185
453 5029519643984426705
454 5313710759229034537
455 5613622671952513205
456 5930106796106711513
457 6264059691769254386
458 6616425411954514839
459 6988197963174063858
460 7380423896693347170
461 7794205025405607065
462 8230701284450677637
463 8691133730516063902
464 9176787699220848088
465 9689016115561994418
466 10229242978191777932
467 10798967012585743327
468 11399765515337120228
469 12033298384755366028
470 12701312361587330706
471 13405645475196544737
472 14148231720721804232
473 14931105962762294985
474 15756409092938655361
475 16626393437144831227
476 17543428441813368849
477 18510006635335125720
478 19528749896081085081
479 20602416023569109829
480 21733905646507813056
481 22926269464741793640
482 24182715861297678662
483 25506618882120750345
484 26901526622361080386
485 28371170017469576244
486 29919472080825165711
487 31550557586935435239
488 33268763245025156856
489 35078648362955583377
490 36985006049626024445
491 38992874956845325432
492 41107551612420163955
493 43334603346646310991
494 45679881867837500651
495 48149537490441314065
496 50750034075574352341
497 53488164689085542764
498 56371068041506898421
499 59406245716770163122
500 62601580258946491970
501 65965354125883320879
502 69506269584287780567
503 73233469557391376700
504 77156559505457962707
505 81285630352815165728
506 85631282547855033423
507 90204651272536791030
508 95017432894523710020
509 100081912681695146777
510 105410993879389129248
511 111018228173707957675
512 116917847649064876203
513 123124798267310126353
514 129654774985078013806
515 136524258541173438044
516 143750554039789733592
517 151351831366369003683
518 159347167571810364980
519 167756591267385066126
520 176601129176795571055
521 185902854893915415786
522 195684940004256804852
523 205971707625562457030
524 216788688538151762355
525 228162679968016813438
526 240121807206926461865
527 252695588140966334211
528 265915000886524672947
529 279812554614487346770
530 294422363777645362146
531 309780225832393473870
532 325923702687052138842
533 342892205979304924419
534 360727086433850494847
535 379471727415365781040
536 399171642948231620832
537 419874580332015177937
538 441630627646219819025
539 464492326288636856497
540 488514788864709691765
541 513755822589150196501
542 540276058543142414349
543 568139086966979017820
544 597411598959573069895
545 628163534785185021057
546 660468239189270589673
547 694402623946334481068
548 730047338074745270142
549 767486945966169332747
550 806810113900420207157
551 848109805220620801703
552 891483484678330569495
553 937033332253453207596
554 984866467000737542727
555 1035095181260515733615
556 1087837185831221269118
557 1143215866477372608309
558 1201360552420152168604
559 1262406797223797816482
560 1326496672778746261304
561 1393779076838068760081
562 1464410054866511527528
563 1538553136706180212167
564 1616379688881488152644
565 1698069283099442168860
566 1783810081836587292126
567 1873799241625646468824
568 1968243335007711121128
569 2067358791825396110484
570 2171372360903659188789
571 2280521592861957339948
572 2395055345192174379713
573 2515234310420640906265
574 2641331568583868329288
575 2773633164917975155287
576 2912438714094679744633
577 3058062031993106052765
578 3210831796452327036587
579 3371092238091428276756
580 3539203862763586736866
581 3715544206837536875690
582 3900508627004793293265
583 4094511125922422562011
584 4297985215532837688801
585 4511384819497505189439
586 4735185216741296563967
587 4969884027683146277274
588 5216002245318163904196
589 5474085312878309709044
590 5744704250419525312466
591 6028456832227638463473
592 6325968817589187022750
593 6637895236999721159688
594 6964921736570773995178
595 7307765982904613931606
596 7667179131431285944875
597 8043947360691319363613
598 8438893475811706682851
599 8852878583892114438251
600 9286803844823444482753
601 9741612300510255406207
602 10218290786316964817998
603 10717871927986643521173
604 11241436228175336610876
605 11790114246152819208918
606 12365088875163033786287
607 12967597721324114320488
608 13598935588941221365045
609 14260457076470277415837
610 14953579288417918703764
611 15679784667805714906954
612 16440623954930835191067
613 17237719277475641891071
614 18072767378183016736270
615 18947542985611716032380
616 19863902334714066991196
617 20823786843252788461067
618 21829226951369013135706
619 22882346130864883039894
620 23985365072130603098034
621 25140606055873734352977
622 26350497518250422839084
623 27617578817202741362248
624 28944505209327944521779
625 30334053045786564503868
626 31789125197362329680790
627 33312756717944672594446
628 34908120757400096357765
629 36578534733933369297425
630 38327466777829652820257
631 40158542457580655468992
632 42075551801288347564324
633 44082456625329391252710
634 46183398184260219556763
635 48382705155010596692628
636 50684901970522863285649
637 53094717517041049089497
638 55617094211482831227311
639 58257197474354184980292
640 61020425616022062065920
641 63912420153168368006355
642 66939076574738252976904
643 70106555575686125054381
644 73421294779455037640515
645 76890020969099400488829
646 80519762849744485821008
647 84317864364036297754637
648 88291998585179336843481
649 92450182211107869871992
650 96800790686450693421081
651 101352573977887740181124
652 106114673031792298014024
653 111096636941984110379838
654 116308440858906212711166
655 121760504670466232528689
656 127463712488474722130656
657 133429432973540780293754
658 139669540535194208062044
659 146196437442935070623616
660 153023076888051201644041
661 160162987034984379630937
662 167630296105410931696452
663 175439758537156221247110
664 183606782264708535251265
665 192147457167070886122293
666 201078584733612819138120
667 210417708997583059947481
668 220183148792162803296126
669 230394031382970839802616
670 241070327536465160878580
671 252232888082757688949115
672 263903482037226819410293
673 276104836344433891504569
674 288860677314074133701511
675 302195773817872947061161
676 316135982322942493482578
677 330708293836363530821896
678 345940882842765810808700
679 361863158316011859627834
680 378505816893528223139562
681 395900898301254060283259
682 414081843125075574501509
683 433083553024149264773691
684 452942453489905040804341
685 473696559254179239472089
686 495385542458837659451556
687 518050803699049245687760
688 541735546061837979968678
689 566484852281501613925431
690 592345765143546565894778
691 619367371268930807504125
692 647600888421100898988387
693 677099756478655733463390
694 707919732227840216208284
695 740118988129647392095234
696 773758215228399845280747
697 808900730369512676502474
698 845612587907003245857239
699 883962696082429976108778
700 924022938270628346218506
701 965868299289047506045993
702 1009576996982055409136068
703 1055230619293369374262332
704 1102914267055272168510700
705 1152716702725454721801126
706 1204730505318832831074359
707 1259052231784300430579412
708 1315782585093959805296517
709 1375026589315464486446049
710 1436893771956833784812691
711 1501498353876722956298161
712 1568959447073080761879212
713 1639401260667335302345223
714 1712953315422505637014696
715 1789750667138489034744319
716 1869934139290430082803483
717 1953650565281637204617424
718 2041053040706665663477633
719 2132301186026522272733781
720 2227561420083701577629515
721 2327007244891952052226399
722 2430819542163138340177769
723 2539186882041688719558909
724 2652305844546417371928220
725 2770381354228657856946988
726 2893627028586905556503429
727 3022265540788434180232866
728 3156528997281711670363055
729 3296659330894933067915274
730 3442908710051594905040645
731 3595539964746866609054796
732 3754827029966526104384375
733 3921055407244519701727641
734 4094522645095792817118447
735 4275538839076925826713213
736 4464427152270452929406142
737 4661524357006369107174753
738 4867181398680625850316828
739 5081763982549939488138962
740 5305653184431693330670818
741 5539246086259302602657951
742 5782956437496255291166089
743 6037215343435877630285806
744 6302471981470344450488449
745 6579194346438736197639853
746 6867870026224302167920798
747 7169007008800030536464139
748 7483134521986147412727919
749 7810803907214999250985188
750 8152589528667755582806458
751 8509089719182342482940251
752 8880927764405780356229844
753 9268752926702484014891654
754 9673241510408969522277697
755 10095097970067499720100374
756 10535056063355577073650176
757 10993880050474298431509967
758 11472365941848847764335920
759 11971342796044867135860057
760 12491674069901015635190244
761 13034259022933216114483466
762 13600034178169420207145957
763 14189974841634034968853717
764 14805096682811733456679088
765 15446457378486234396170902
766 16115158322467986064437074
767 16812346403796564286259333
768 17539215856130275152528317
769 18297010181113838045434479
770 19087024148650637626004795
771 19910605877091464908979916
772 20769158996496858423499580
773 21664144898223213827734797
774 22597085074238290389245820
775 23569563549673050613019721
776 24583229412283241457907419
777 25639799442604356032256998
778 26741060848761895979897398
779 27888874110018733335309208
780 29085175933332315019095660
781 30331982327324761569843174
782 31631391798273436576449328
783 32985588672871142494724560
784 34396846552724188059428776
785 35867531905710329694993907
786 37400107799553298053149390
787 38997137783137532957766099
788 40661289921338210664562499
789 42395340989322765148414623
790 44202180832549532759944796
791 46084816898885605762040394
792 48046378949554676977947281
793 50090123955838671656402503
794 52219441188766326779313110
795 54437857509252760594303548
796 56749042866485606607077798
797 59156816012603449977770946
798 61665150442067610468867534
799 64278180564399280814283115
800 67000208119334836174903044
801 69835708843745529734118045
802 72789339400075948007095752
803 75865944576373192643078634
804 79070564768416249601575853
805 82408443754798685765631432
806 85885036776286772316504084
807 89506018931146932643248402
808 93277293898639120965497424
809 97205003003274843938155045
810 101295534632977442819514938
811 105555534024717020471249680
812 109991913431770126719044257
813 114611862687224270688413516
814 119422860178966699173781099
815 124432684251904742896315281
816 129649425053829063349996647
817 135081496841879826234231405
818 140737650767287758420703063
819 146626988156654708374002556
820 152758974308801634887809498
821 159143452826851957156578016
822 165790660506036600956313246
823 172711242798398055912123779
824 179916269876448251310552915
825 187417253318580904546974340
826 195226163439979861619989551
827 203355447293569847992823303
828 211818047366564875032839102
829 220627420999037994503271390
830 229797560552017803971014368
831 239343014353553928118435445
832 249278908452353571277970283
833 259620969209601619216709519
834 270385546760820452337752477
835 281589639380715144082010911
836 293250918785283279520293768
837 305387756406643245734687130
838 318019250677464782984115738
839 331165255363151725752225349
840 344846408981460139805640275
841 359084165350599614988440507
842 373900825308509556382476400
843 389319569647472676299821200
844 405364493309990780219308133
845 422060640893432043143947229
846 439434043512849243987899349
847 457511757073074790391092019
848 476321902003225207990525675
849 495893704508585531632164426
850 516257539397017296035832561
851 537444974539012792591719141
852 559488817022848486773071028
853 582423161068421187026155812
854 606283437765849058432871919
855 631106466707213281890133776
856 656930509582495051111487652
857 683795325813231425501888865
858 711742230300285813599419353
859 740814153364785791561626135
860 771055702964360487971381157
861 802513229269668723488946807
862 835234891689510786885278633
863 869270728435892648614854913
864 904672728723951225675149427
865 941494907704958207914167456
866 979793384234414980621237682
867 1019626461580810218313472660
868 1061054711184680269215047507
869 1104141059581440042335682738
870 1148950878605813778322051023
871 1195552078999810964252986005
872 1244015207550868447257704132
873 1294413547891205117060643609
874 1346823225094447938124576995
875 1401323314210345536766081006
876 1457995952883758655462765489
877 1516926458209230620677438703
878 1578203447978200563998165997
879 1641918966481418416881959510
880 1708168615035294394731990846
881 1777051687406822318138887252
882 1848671310318333480026012311
883 1923134589219684651211331862
884 2000552759522576500265523421
885 2081041343498517869420970918
886 2164720313049553245724009820
887 2251714258568196534471365929
888 2342152564111161630769536071
889 2436169589119349419502858173
890 2533904856925282553271455684
891 2635503250297631234497291349
892 2741115214281830851552754467
893 2850896966604869117107754106
894 2965010715922348378647637467
895 3083624888195675664922794952
896 3206914361497979079078879357
897 3335060709557814510143459805
898 3468252454361241679031575823
899 3606685328144084166895462200
900 3750562545118526659488166027
901 3900095083290264012217443920
902 4055501976735637242243009828
903 4217010618721138047134673695
904 4384857076061828331172546702
905 4559286415129116416741605269
906 4740553039933507710233967732
907 4928921042722859555729434778
908 5124664567552928823230574933
909 5328068187303002361818708427
910 5539427294626818491369369124
911 5759048507346156894628650297
912 5987250088813133388044501962
913 6224362383785656308194230342
914 6470728270380489000522512592
915 6726703628688123544680608362
916 6992657826655080896653945717
917 7268974223860449254730135158
918 7556050693836404976682015054
919 7854300165605195268381404130
920 8164151185129624015108899819
921 8486048497398464723263398307
922 8820453649894530927516645207
923 9167845618219281814414041451
924 9528721454676013995484209709
925 9903596960641727831374066648
926 10293007383587927757218706397
927 10697508139640677604641598271
928 11117675562602540991150724780
929 11554107680391265820639988353
930 12007425019884668902695257428
931 12478271441195726429283879490
932 12967315002438921143758929681
933 13475248856085931510676566235
934 14002792178048412749205220072
935 14550691130665314195099933277
936 15119719860814644623340605026
937 15710681534412139451792055732
938 16324409408604749334883531303
939 16961767943012460182088773851
940 17623653951420627960758594985
941 18310997795373864857115709780
942 19024764621174618160471599668
943 19765955641841928426539704184
944 20535609465641628878983424349
945 21334803472855330301937325354
946 22164655242515237288952471078
947 23026324030891923172395473510
948 23921012303586091935394504986
949 24849967323139716170735358434
950 25814482794150332420261494214
951 26815900567941214727051659281
952 27855612408913342748866010442
953 28935061824778919073820652780
954 30055745962954522473770622437
955 31219217575471062985612661111
956 32427087054841529557913668708
957 33681024543412206576520011899
958 34982762118812733731549164955
959 36334096058211066348486407028
960 37736889184175371313663854656
961 39193073295041990919078455086
962 40704651682791299161667200767
963 42273701741537232796274616629
964 43902377669846149844158797682
965 45592913270211963165822624492
966 47347624849132040921429255026
967 49168914221347506948569044278
968 51059271821937321515899944734
969 53021279930083054338766476009
970 55057616008455777827924405036
971 57171056162313011243161930413
972 59364478722537535053091351263
973 61640867956995989440077316067
974 64003317914749077004644132744
975 66455036407801539220632740493
976 68999349135244688525185018194
977 71639703954811590328284126336
978 74379675307041043216760631525
979 77222968797425537107953843524
980 80173425942106650059274175002
981 83235029082872902515665744441
982 86411906477416434173448825851
983 89708337571009815631989510255
984 93128758455979614048961501095
985 96677767525572588699822777993
986 100360131329040615771680302183
987 104180790635004991213972019463
988 108144866710406920574695967289
989 112257667822601896699835054047
990 116524695972418852086334242349
991 120951653866273327685229249494
992 125544452135705274254792763492
993 130309216812999116687782697060
994 135252297071844515335844953522
995 140380273242303208987337951799
996 145699965109668881462014165919
997 151218440507135243797814567476
998 156943024212531248521038391931
999 162881307159733356729153262814
1000 169041155975732178918590715989