2 1
3 0
4 2
5 2
6 3
7 5
8 9
9 10
10 16
11 23
12 31
13 43
14 60
15 75
16 106
17 140
18 179
19 237
20 310
21 389
22 508
23 647
24 815
25 1032
26 1305
27 1617
28 2033
29 2527
30 3117
31 3857
32 4764
33 5812
34 7142
35 8711
36 10585
37 12866
38 15605
39 18803
40 22716
41 27325
42 32774
43 39286
44 47016
45 56019
46 66819
47 79456
48 94273
49 111766
50 132305
51 156168
52 184340
53 217114
54 255276
55 299865
56 351803
57 411861
58 481977
59 563086
60 656906
61 765682
62 891461
63 1036202
64 1203757
65 1396516
66 1618229
67 1873534
68 2166925
69 2503023
70 2889358
71 3331620
72 3837658
73 4416996
74 5079257
75 5834518
76 6697677
77 7681222
78 8801344
79 10077313
80 11528977
81 13177757
82 15052625
83 17179982
84 19592579
85 22328593
86 25428288
87 28935337
88 32905809
89 37393744
90 42463842
91 48190808
92 54654241
93 61941147
94 70158932
95 79414865
96 89834902
97 101562605
98 114752475
99 129574130
100 146230632
101 164930583
102 185914515
103 209454564
104 235845533
105 265411276
106 298531716
107 335603881
108 377080367
109 423469998
110 475325748
111 533256006
112 597962428
113 670188107
114 750772482
115 840653660
116 940854407
117 1052499083
118 1176868997
119 1315333461
120 1469427722
121 1640860551
122 1831496695
123 2043385525
124 2278840436
125 2540348461
126 2830682920
127 3152918044
128 3510411457
129 3906850164
130 4346364522
131 4833414458
132 5372949154
133 5970437688
134 6631854481
135 7363752179
136 8173428911
137 9068785586
138 10058556967
139 11152368867
140 12360732798
141 13695165597
142 15168431053
143 16794371753
144 18588242379
145 20566811179
146 22748381649
147 25152981564
148 27802720045
149 30721598586
150 33935992915
151 37474834409
152 41369679108
153 45655013924
154 50368784060
155 55552198705
156 61250437301
157 67512956790
158 74393658452
159 81951376755
160 90250661611
161 99361620785
162 109360952026
163 120332465787
164 132367422618
165 145565310397
166 160035019432
167 175894784481
168 193273712278
169 212312651667
170 233164824508
171 255997066970
172 280991590905
173 308346159942
174 338276357147
175 371017012484
176 406823340323
177 445972899134
178 488768258944
179 535537625979
180 586638221184
181 642458612257
182 703420677219
183 769982705430
184 842643441837
185 921943520331
186 1008470535122
187 1102862792301
188 1205812640078
189 1318071345886
190 1440455241053
191 1573848571154
192 1719211110019
193 1877584172070
194 2050096137837
195 2237970090816
196 2442533186225
197 2665221861660
198 2907593325934
199 3171335105180
200 3458274065125
201 3770388343864
202 4109821618946
203 4478892221517
204 4880110485629
205 5316193795504
206 5790081155960
207 6304951726922
208 6864246583210
209 7471684119708
210 8131286269243
211 8847402099512
212 9624731041868
213 10468351605411
214 11383754522053
215 12376868158525
216 13454098176796
217 14622364271129
218 15889136899343
219 17262481559506
220 18751109204291
221 20364417434107
222 22112550415414
223 24006455808428
224 26057942329256
225 28279747740339
226 30685615441899
227 33290360204350
228 36109958662319
229 39161637029024
230 42463960616194
231 46036937864794
232 49902136393390
233 54082786692697
234 58603918565532
235 63492495585327
236 68777553420092
237 74490358298712
238 80664582495119
239 87336466196752
240 94545022827244
241 102332244231453
242 110743312993554
243 119826842956744
244 129635143834948
245 140224471654128
246 151655337145260
247 163992817322223
248 177306879595605
249 191672745366415
250 207171287887271
251 223889416835403
252 241920540303278
253 261365035963376
254 282330743133761
255 304933510303233
256 329297791665898
257 355557233483276
258 383855364523595
259 414346305460456
260 447195512153982
261 482580597162270
262 520692221299660
263 561734982280867
264 605928443701959
265 653508198743260
266 704726987729629
267 759855926048932
268 819185832671965
269 883028569228902
270 951718569194867
271 1025614426679699
272 1105100569058813
273 1190589085914330
274 1282521702396908
275 1381371786544596
276 1487646615424552
277 1601889738968093
278 1724683472935800
279 1856651613355186
280 1998462358491506
281 2150831303560373
282 2314524788945393
283 2490363404392075
284 2679225689487559
285 2882052148374210
286 3099849562977996
287 3333695440464847
288 3584742945898261
289 3854226078193504
290 4143465141681560
291 4453872664134276
292 4786959743613079
293 5144342625744900
294 5527749949011190
295 5939030363414206
296 6380160590958869
297 6853254120244192
298 7360570517310367
299 7904525113619500
300 8487699616862644
301 9112853287559277
302 9782934770667317
303 10501094828605863
304 11270699958570034
305 12095346608181230
306 12978876669965616
307 13925393823327414
308 14939280842218995
309 16025218183421831
310 17188203842366318
311 18433574137248369
312 19767026268965732
313 21194642139930288
314 22722913587901155
315 24358769438468628
316 26109604372312411
317 27983309207058569
318 29988303650954575
319 32133570911386564
320 34428694366313612
321 36883896817138752
322 39510082334850724
323 42318880233660946
324 45322692489917504
325 48534743875899579
326 51969135087514920
327 55640899531851937
328 59566063815274258
329 63761711394847577
330 68246051037701409
331 73038489231309099
332 78159706918941868
333 83631741419561015
334 89478073617650842
335 95723719813566804
336 102395330289345939
337 109521293592827368
338 117131847046634638
339 125259194591074150
340 133937632117852879
341 143203679617189043
342 153096222707474244
343 163656662403767470
344 174929073810564620
345 186960375175116674
346 199800507568098614
347 213502624456423445
348 228123294388200361
349 243722715495605475
350 260364942747528988
351 278118129817627398
352 297054785997368098
353 317252047388422171
354 338791966414792103
355 361761818220095925
356 386254425220824331
357 412368502242834068
358 440209022915236101
359 469887606567060419
360 501522930709111370
361 535241167553790808
362 571176446306426036
363 609471344399093578
364 650277408695339768
365 693755705995764839
366 740077409254086427
367 789424417895078282
368 841990014607696587
369 897979562763242644
370 957611246002095121
371 1021116849518105775
372 1088742591142198016
373 1160750000653447373
374 1237416850565616167
375 1319038143837456513
376 1405927160791369608
377 1498416565137972278
378 1596859579381718604
379 1701631228222624430
380 1813129654405317616
381 1931777514188702692
382 2058023455773619814
383 2192343681215882514
384 2335243604891075440
385 2487259607554012498
386 2648960892096852253
387 2820951450469390290
388 3003872146597410283
389 3198402916826520922
390 3405265104563727874
391 3625223928950696436
392 3859091095934225286
393 4107727564256553140
394 4372046473307145765
395 4653016235906235076
396 4951663817365013954
397 5269078201977047213
398 5606414058412801211
399 5964895620616534311
400 6345820794104110251
401 6750565493047633206
402 7180588235558745913
403 7637435000430254117
404 8122744361052163057
405 8638252918553933047
406 9185801048202357507
407 9767338967840625782
408 10384933163699018681
409 11040773180050636736
410 11737178794234905825
411 12476607606398856191
412 13261663063722970931
413 14095102932855185452
414 14979848266228249734
415 15918992873535372624
416 16915813327818301792
417 17973779545283587753
418 19096565966574958477
419 20288063360288110230
420 21552391307969772407
421 22893911388911313126
422 24317241104998102482
423 25827268597829490497
424 27429168196819689896
425 29128416829090973295
426 30930811368232722244
427 32842486950381630489
428 34869936312615706680
429 37020030223425651226
430 39300039059098129111
431 41717655570934228960
432 44281018943849129663
433 46998740189298772926
434 49879928947546487298
435 52934221792571287996
436 56171812114214864673
437 59603481642203867589
438 63240633743579384018
439 67095328556943713559
440 71180320065732345668
441 75509095235381089499
442 80095915317392049898
443 84955859412348177283
444 90104870464339497803
445 95559803778914266750
446 101338478203644249933
447 107459730138487393662
448 113943470517754862742
449 120810744893615430749
450 128083796847770166580
451 135786134863393658780
452 143942602846353574210
453 152579454519633789232
454 161724431885597218569
455 171406847938174035702
456 181657673923368951956
457 192509631335534613513
458 203997288905944108305
459 216157164883597982266
460 229027834874698317710
461 242650045494378928943
462 257066834224201494198
463 272323655739156921772
464 288468515051836812749
465 305552107875520702168
466 323627968569963256215
467 342752626021123182607
468 362985767974547038173
469 384390414190775010204
470 407033098893295495855
471 430984063047070119877
472 456317456963108224109
473 483111553713324885587
474 511448974042846024502
475 541416923291099681735
476 573107440957606031734
477 606617663632735785778
478 642050101966778280614
479 679512932342060060403
480 719120304157555345698
481 760992663431991898781
482 805257093583628216098
483 852047674350583019305
484 901505859764728777979
485 953780876088275187536
486 1009030140917541808851
487 1067419704424075531464
488 1129124713889634252681
489 1194329902824192101367
490 1263230105902400828001
491 1336030800957648974607
492 1412948679629796844451
493 1494212247994220645261
494 1580062458728482502255
495 1670753376539773946828
496 1766552878521525984803
497 1867743391122872437918
498 1974622665846683913074
499 2087504595486163989148
500 2206720072991376860147
501 2332617895267340302738
502 2465565714152405062049
503 2605951036858202512131
504 2754182278676089177000
505 2910689870409397824211
506 3075927423337902338288
507 3250372954786399138815
508 3434530177322795162271
509 3628929854668513225127
510 3834131228039920976416
511 4050723516252099967704
512 4279327493345526663510
513 4520597147832278638380
514 4775221427624763514729
515 5043926074802809363605
516 5327475555148632871154
517 5626675086949436768235
518 5942372774099838463151
519 6275461848962367243502
520 6626883030433159986849
521 6997627002802458151305
522 7388737021942705946460
523 7801311654886550552912
524 8236507659519182345725
525 8695543011650749540381
526 9179700086759496882316
527 9690329003907477437015
528 10228851140483254232201
529 10796762825919237567423
530 11395639223357140355852
531 12027138408924028892556
532 12693005658361218765588
533 13395077951054062263251
534 14135288702922200478502
535 14915672739095970867908
536 15738371518337495371206
537 16605638622043415416342
538 17519845520827196028318
539 18483487632113542399311
540 19499190683910519047658
541 20569717399379340064219
542 21697974518116915560621
543 22887020171188276885678
544 24140071627223849029675
545 25460513427505916884304
546 26851905930101782933246
547 28317994282567861150769
548 29862717844377458442045
549 31490220081660122981873
550 33204858957284141368165
551 35011217840158714465067
552 36914116960264628126785
553 38918625435437942778919
554 41030073897983851208257
555 43254067751036219159103
556 45596501085253902734598
557 48063571287605857529133
558 50661794377254023978391
559 53398021103160434800537
560 56279453840638623555395
561 59313664326427270944998
562 62508612272860138295709
563 65872664903289804904715
564 69414617454962868704135
565 73143714695339206582674
566 77069673501132482275366
567 81202706552376509906686
568 85553547195257817975284
569 90133475529600577664809
570 94954345781914974567196
571 100028615024998350914291
572 105369373309246627579663
573 110990375274724873028778
574 116906073315079305475755
575 123131652367265520505543
576 129683066407333362117111
577 136577076733016611568538
578 143831292119175731028352
579 151464210937147634698677
580 159495265331898034062230
581 167944867554752618627475
582 176834458557315198573006
583 186186558953318818365305
584 196024822461906540219555
585 206374091952282892788722
586 217260458213604895137729
587 228711321579166537061565
588 240755456543744059343546
589 253423079515008711838403
590 266745919848525956554508
591 280757294324161294879237
592 295492185227093950407659
593 310987322203542599568577
594 327281268073631275724983
595 344414508787130604509176
596 362429547718812089085199
597 381371004510851225721370
598 401285718677032703813657
599 422222858192670773677088
600 444234033309668229406298
601 467373415841202078473562
602 491697864174597115551288
603 517267054284741182388593
604 544143617030282955473113
605 572393282026972761281159
606 602085028412066774100653
607 633291242821189321315620
608 666087884917068283802107
609 700554660827344563258829
610 736775204861943238118989
611 774837269896487467147917
612 814832926832948386691404
613 856858773559473849093960
614 901016153854433047861739
615 947411386702653730282419
616 996156006509598815639719
617 1047367014720283345609861
618 1101167143381008384903515
619 1157685131197154774149594
620 1217056012669898743881277
621 1279421420924299549604957
622 1344929904864875812885525
623 1413737261322442737462809
624 1486006882895625109285387
625 1561910122211547131605105
626 1641626673368209812905924
627 1725344971359228432398155
628 1813262610313005620216788
629 1905586781414666852302295
630 2002534731429403599160840
631 2104334242774846307386615
632 2211224136138887909673414
633 2323454796688593646049376
634 2441288724957361413090123
635 2565001113544925896922960
636 2694880450828746879550415
637 2831229152924767217258655
638 2974364225198196842668423
639 3124617954688435803877383
640 3282338634867003485830115
641 3447891324209283917670333
642 3621658640142250432539716
643 3804041589983609993362577
644 3995460440568309397520837
645 4196355628340144786177031
646 4407188711758209937208446
647 4628443367948680779081123
648 4860626435636027136278097
649 5104269006459227358623652
650 5359927566881978550813049
651 5628185193011305064740626
652 5909652800733392393872025
653 6204970453680607601794654
654 6514808731675681535872280
655 6839870162394404913720258
656 7180890719121044885232819
657 7538641387606472831890472
658 7913929805162553656446951
659 8307601975263001692853528
660 8720544061089247932775226
661 9153684261586498938858077
662 9607994773765822613129304
663 10084493845162934126020817
664 10584247920525693358552195
665 11108373886979700352497533
666 11658041422136143793565336
667 12234475449773481514858078
668 12838958707943706056039859
669 13472834434578965738022938
670 14137509175884563387231839
671 14834455723034271554984800
672 15565216182958010135598499
673 16331405189232453802088987
674 17134713259366553803574267
675 17976910305063411398246765
676 18859849302313427857594908
677 19785470128471289974735520
678 20755803573819287112965640
679 21772975535408942586394181
680 22839211401334168714026932
681 23956840633961291916938999
682 25128301560996418790504940
683 26356146383655431606521394
684 27643046411648719368437691
685 28991797535071634084442398
686 30405325943755161537671021
687 31886694105109460827268027
688 33439107011953306237641676
689 35065918712319403665027983
690 36770639133796116843513982
691 38556941215460683218722071
692 40428668361053478937058494
693 42389842227656927713103808
694 44444670864738554145039875
695 46597557219058667066109833
696 48853108021671727182623574
697 51216143073894376155498665
698 53691704949875227719448174
699 56285069134189539115187308
700 59001754613652081851667231
701 61847534943367387391925159
702 64828449807966786007203204
703 67950817099818192361824063
704 71221245536971141088706331
705 74646647844610222365625492
706 78234254524784153524803881
707 81991628240240610071803886
708 85926678839384488914004427
709 90047679050461782396513772
710 94363280874321878892395714
711 98882532706406418833222719
712 103614897219894176221016478
713 108570270043297938847709935
714 113758999267325037675823568
715 119191905817216462284915338
716 124880304728380244191521437
717 130836027364793823796295894
718 137071444621299617276029305
719 143599491152673031223366624
720 150433690674276090555312455
721 157588182380922375067116347
722 165077748532626607270390735
723 172917843258035657636743551
724 181124622628458570626281613
725 189714976057664977926561023
726 198706559085087999345630739
727 208117827602404949643834236
728 217968073586086880613110427
729 228277462401223880671123616
730 239067071744656701124262153
731 250358932298331524723304502
732 262176070166939829083282649
733 274542551176914380604073111
734 287483527117196747429114809
735 301025284005662928929999971
736 315195292468587517217076532
737 330022260324222757682995022
738 345536187465577292088570658
739 361768423141347739586400807
740 378751725738226196343603423
741 396520325172240138535786445
742 415109988001258058151491014
743 434558085375522522425941151
744 454903663948178638154325805
745 476187519872732020437423161
746 498452276019818398991799948
747 521742462551325214283150704
748 546104600995635912684890479
749 571587291973811222051270455
750 598241306733023354378983029
751 626119682649926026945011012
752 655277822873589684632160792
753 685773600284847477205176094
754 717667465956224813012001281
755 751022562304342934924251601
756 785904841134961006031058643
757 822383186788973819574323651
758 860529544606533278604717627
759 900419054935658161320346344
760 942130192921056483056401480
761 985744914318731383973253285
762 1031348807592465310362353555
763 1079031252558703827832258739
764 1128885585857630327785064160
765 1181009273539934276595510930
766 1235504091070720094712031935
767 1292476311064555684415402620
768 1352036899079037444155908237
769 1414301717807567991623885986
770 1479391740026382669760056297
771 1547433270665764189521536783
772 1618558178390613037880449910
773 1692904137091528043412278436
774 1770614877704547336470095463
775 1851840450794695901502213996
776 1936737500356719115978552975
777 2025469549305332871592934172
778 2118207297146717731945183551
779 2215128930343328868518244081
780 2316420445905672953586221117
781 2422275988766367441992199928
782 2532898203514964894177066962
783 2648498601096105939299042631
784 2769297941098248531490354066
785 2895526630286089112593333670
786 3027425138057173692673593317
787 3165244429530783204829989709
788 3309246417006593063083869433
789 3459704430561183682852355066
790 3616903708581863186426528750
791 3781141909070127842259340887
792 3952729642581809966109072336
793 4131991027706055309326796892
794 4319264270022594581119688470
795 4514902265515570427877625056
796 4719273229462050045383638199
797 4932761351855072713194566976
798 5155767480465088138933746400
799 5388709832688238905307557170
800 5632024737377261817559820557
801 5886167407899973374904537490
802 6151612747720908129251988403
803 6428856189854596046759850156
804 6718414571594699651836776474
805 7020827045979855636960140457
806 7336656031517022169875824673
807 7666488201745456625557509650
808 8010935516288623072521578368
809 8370636295108397279383099048
810 8746256337746479738767220008
811 9138490089409755143091758637
812 9548061855832248116639030073
813 9975727068925230943482074058
814 10422273605308357064879029250
815 10888523159899631684869178335
816 11375332676831257821397908777
817 11883595840049429475755761081
818 12414244626052187546132654020
819 12968250921319282836426317412
820 13546628207090948051496494088
821 14150433314259965480769177092
822 14780768251254203238209391469
823 15438782107902066671931341689
824 16125673038394741850758819674
825 16842690326585317265900702793
826 17591136536995121378098479808
827 18372369755033527597020632675
828 19187805920079950398521774812
829 20038921255222601342406903806
830 20927254797601992756466272755
831 21854411033466624508290222551
832 22822062642212940871951063446
833 23831953353853377847608209164
834 24885900924536174257899532102
835 25985800234924990872147907356
836 27133626516440080923724853750
837 28331438710564052894985328082
838 29581382966623242332888893698
839 30885696283672541032347721671
840 32246710302338423677768186214
841 33666855252707796176146046962
842 35148664064594674574278166660
843 36694776646770656765751612873
844 38307944342007648835724592809
845 39991034565054879733400489674
846 41747035630958282140606416054
847 43579061781424245438705214581
848 45490358417237866557506429361
849 47484307545065984066176628491
850 49564433447306349327256379185
851 51734408583989197709727821100
852 53998059736097863139409460364
853 56359374400045761840923605501
854 58822507443435281035627818056
855 61391788032627454905586032841
856 64071726843068548920717842613
857 66867023563754209851592684977
858 69782574707665574479028257178
859 72823481740478850965652216512
860 75995059540338670281657920429
861 79302845201993303658748451536
862 82752607199115294639066575699
863 86350354919178118709712132244
864 90102348585830382796660065622
865 94015109584297281219548707790
866 98095431205954019067710625035
867 102350389828854777410800047598
868 106787356551662049043096298187
869 111414009299109422145257157838
870 116238345417848735766810083915
871 121268694782272654282367617617
872 126513733430676980404984162763
873 131982497752930238389687772427
874 137684399251649618722845647789
875 143629239899747642157249810619
876 149827228118115929443202575367
877 156288995398143060503923893931
878 163025613594735140726545180143
879 170048612916516852315422878785
880 177370000640935758483814929049
881 185002280583079692282034870050
882 192958473348149792457410796436
883 201252137398700995898593913313
884 209897390968981862880815317243
885 218908934859972679764498348500
886 228302076150033068435750217582
887 238092752857435115968743569881
888 248297559592479554949861796942
889 258933774238360578675704747516
890 270019385701475882855499145732
891 281573122773468360976046876970
892 293614484148932695571600145201
893 306163769644432386038016917520
894 319242112666255534129319687143
895 332871513976179637896816275441
896 347074876806435577311397989739
897 361876043377054486316602674323
898 377299832870846423680318480538
899 393372080923406618171038532014
900 410119680687779487828380096815
901 427570625535720056547801346107
902 445754053459898480032900503824
903 464700293243891447988350469918
904 484440912469392408004913053541
905 505008767432762490069402239615
906 526438055045842714141161146576
907 548764366798841656234939613619
908 572024744866126146795043640889
909 596257740438870843967913610916
910 621503474371763929078454904261
911 647803700234334339393406960582
912 675201869860969220655081849779
913 703743201497313365529510450794
914 733474750644513979105360129863
915 764445483706689072268426253756
916 796706354551054605594596470175
917 830310384094360176409174566032
918 865312743033665487238568626064
919 901770837844023294581196161655
920 939744400170352042530005787232
921 979295579745677751707096962311
922 1020489040972998789762431111007
923 1063392063313297673286041672899
924 1108074645627702887741709190465
925 1154609614627472566891477446915
926 1203072737591368826955216070859
927 1253542839516111474317691467332
928 1306101924871942066028830711785
929 1360835304141915986619494403241
930 1417831725330385474609471599341
931 1477183510633220524378206137772
932 1538986698469681251873759538211
933 1603341191083499756577897626119
934 1670350907928651884287086149328
935 1740123945063525610994156165916
936 1812772740785739990210741215032
937 1888414247748715304761048099667
938 1967170111810292013112289580189
939 2049166857873238878909146442865
940 2134536082987380563048104071011
941 2223414656993342625881922108129
942 2315944930998577687438431295470
943 2412274953987377479480648208437
944 2512558697878050420864023261069
945 2616956291352349576782616953535
946 2725634262794574167398560455864
947 2838765792690575417848067363443
948 2956530975850198956167812811642
949 3079117093830466819929960740577
950 3206718897951110432650723625511
951 3339538903308909333988834401266
952 3477787694212673760602060589473
953 3621684241476675252913434901134
954 3771456232026907763576379727889
955 3927340411291726718084750762648
956 4089582938866243980062302482976
957 4258439757958352205317192486344
958 4434176979143420084953959405894
959 4617071278974591269842638844352
960 4807410314016269855761273071114
961 5005493150889757758971563841768
962 5211630712942215678525852977609
963 5426146244173151686562648106940
964 5649375791076510798364431918152
965 5881668703081205405350279261341
966 6123388152298633096902296498879
967 6374911673312348301108238935648
968 6636631723772693785901239652630
969 6908956266587862946029180013114
970 7192309374532569545377608156658
971 7487131858126319773607257327767
972 7793881917665263971062755190834
973 8113035820324725565915222992557
974 8445088603283886592798367942907
975 8790554803859762895179672425257
976 9149969217674549288793328682342
977 9523887685918740746649109675191
978 9912887912812202840306450086179
979 10317570314406547769315525159923
980 10738558899914915857241476478970
981 11176502186799582896341192799399
982 11632074150893740357708133266412
983 12105975212881429714142536295711
984 12598933262509030040005661876469
985 13111704721952876548483219921814
986 13645075649820695591839116632589
987 14199862887319603560985042170858
988 14776915248180472012598565161341
989 15377114753987630271434424115045
990 16001377916624252016955121824232
991 16650657069607334835085876282472
992 17325941750152128833865470584413
993 18028260133874237467591672510990
994 18758680524108452037697214099316
995 19518312897896835539078944434429
996 20308310510774753698306516379004
997 21129871562562448166149032640665
998 21984240926451590193749259662178
999 22872711943761091684795903433795
1000 23796628286824351350524742240118