5 5
6 0
7 6
8 6
9 13
10 18
11 34
12 35
13 66
14 82
15 120
16 154
17 230
18 286
19 408
20 514
21 699
22 886
23 1189
24 1485
25 1949
26 2441
27 3136
28 3906
29 4980
30 6159
31 7757
32 9555
33 11908
34 14600
35 18062
36 22000
37 27028
38 32804
39 39996
40 48327
41 58614
42 70489
43 85036
44 101876
45 122284
46 145943
47 174419
48 207354
49 246804
50 292463
51 346697
52 409477
53 483754
54 569511
55 670565
56 787152
57 923843
58 1081444
59 1265544
60 1477366
61 1724055
62 2007555
63 2336481
64 2714035
65 3150920
66 3651421
67 4229078
68 4889991
69 5650637
70 6519761
71 7517708
72 8656018
73 9960368
74 11446124
75 13144672
76 15076824
77 17281500
78 19785533
79 22637498
80 25872405
81 29549850
82 33715658
83 38443410
84 43791458
85 49851401
86 56697714
87 64442755
88 73182071
89 83054175
90 94179293
91 106728760
92 120854268
93 136765897
94 154655096
95 174779924
96 197379293
97 222771101
98 251253522
99 283215200
100 319028501
101 359169399
102 404098838
103 454400268
104 510644255
105 573542488
106 643800799
107 722287429
108 809870616
109 907610133
110 1016572955
111 1138047373
112 1273343901
113 1424028728
114 1591704009
115 1778273241
116 1985693506
117 2216271471
118 2472395433
119 2756858836
120 3072566560
121 3422900344
122 3811389288
123 4242116972
124 4719366704
125 5248066549
126 5833400797
127 6481312312
128 7198069411
129 7990824282
130 8867147538
131 9835639460
132 10905423639
133 12086834068
134 13390853122
135 14829875913
136 16417108679
137 18167406132
138 20096618861
139 22222533495
140 24564154144
141 27142746219
142 29981070290
143 33104527650
144 36540334516
145 40318806180
146 44472451861
147 49037402145
148 54052449657
149 59560616930
150 65608128776
151 72246168227
152 79529760640
153 87519724239
154 96281494828
155 105887273759
156 116414779828
157 127949653169
158 140584110454
159 154419618237
160 169565492121
161 186141844320
162 204278111749
163 224116355103
164 245809693294
165 269525974686
166 295446167015
167 323768416115
168 354706381637
169 388493779249
170 425382639711
171 465648369666
172 509588002896
173 557525805173
174 609811509940
175 666826597274
176 728982499085
177 796727603923
178 870545520877
179 950962857215
180 1038547550480
181 1133917584543
182 1237739383465
183 1350737550660
184 1473693449262
185 1607456040161
186 1752940674223
187 1911141253726
188 2083129256332
189 2270067342790
190 2473208783120
191 2693912635193
192 2933643638340
193 3193989259490
194 3476660105964
195 3783509032806
196 4116532317978
197 4477891021076
198 4869913037900
199 5295117116959
200 5756215914129
201 6256142949419
202 6798057001322
203 7385372303101
204 8021764486676
205 8711204571506
206 9457966669758
207 10266666196052
208 11142269827129
209 12090138378389
210 13116039361985
211 14226195298334
212 15427299243779
213 16726569165457
214 18131767137568
215 19651260462149
216 21294045091891
217 23069814558083
218 24988988218532
219 27062788925765
220 29303277121745
221 31723438253100
222 34337223578549
223 37159648825672
224 40206842667832
225 43496157988241
226 47046229491420
227 50877099076829
228 55010283928809
229 59468918089624
230 64277832505830
231 69463714806612
232 75055203439097
233 81083067854100
234 87580318756317
235 94582411662466
236 102127375530839
237 110256042605581
238 119012198500228
239 128442841562933
240 138598357471704
241 149532812302421
242 161304155033745
243 173974548563617
244 187610604579958
245 202283757233102
246 218070534899705
247 235052982454926
248 253318975008351
249 272962694904755
250 294084993855274
251 316793931509119
252 341205192673308
253 367442695876436
254 395639073157984
255 425936357488843
256 458486534394793
257 493452318109940
258 531007784819625
259 571339249512239
260 614645991831677
261 661141246353984
262 711053034347774
263 764625281716005
264 822118770920985
265 883812403557529
266 950004288420556
267 1021013166975484
268 1097179656652950
269 1178867859624885
270 1266466781948540
271 1360392149716452
272 1461088027203283
273 1569028866476317
274 1684721351803112
275 1808706711933613
276 1941562820488814
277 2083906804973057
278 2236397436465326
279 2399738072552558
280 2574679375217449
281 2762022629295783
282 2962622831149001
283 3177392430824341
284 3407304839293647
285 3653398647140127
286 3916781605624569
287 4198635381033739
288 4500220070408702
289 4822879559520379
290 5168046641432333
291 5537249052958588
292 5932115274433466
293 6354381328383770
294 6805897346987636
295 7288635228742461
296 7804696070538308
297 8356318788040874
298 8945888523138941
299 9575946346316939
300 10249198762064397
301 10968528627847294
302 11737005894705460
303 12557899891794118
304 13434691458333533
305 14371086760250042
306 15371030986538470
307 16438723886870644
308 17578635226057007
309 18795522251879454
310 20094447127157690
311 21480796561687672
312 22960301465530501
313 24539059009381786
314 26223554771449509
315 28020687519526886
316 29937794159229195
317 31982677565270848
318 34163634672830899
319 36489487727222006
320 38969615900314350
321 41613990368418517
322 44433209884049831
323 47438540139509252
324 50641953772117726
325 54056174527899743
326 57694722234102451
327 61571962334338006
328 65703156428484337
329 70104517816567968
330 74793268272931707
331 79787700314054646
332 85107240951083805
333 90772521476035927
334 96805449027335872
335 103229284780057815
336 110068724252153420
337 117349984890735670
338 125100896153205420
339 133350997591630344
340 142131639866879311
341 151476094558728077
342 161419667399911609
343 171999821184929622
344 183256302657748832
345 195231280044294399
346 207969485196597134
347 221518367446688850
348 235928252787986719
349 251252515946418863
350 267547758581401398
351 284874001679576822
352 303294884988457756
353 322877882074896680
354 343694523449267062
355 365820636900855386
356 389336597046794644
357 414327593844205678
358 440883911612233930
359 469101228944760591
360 499080930589925524
361 530930442354542339
362 564763579603071382
363 600700921138949000
364 638870198512402975
365 679406713305979630
366 722453771900126109
367 768163151089418305
368 816695583469991507
369 868221276850973968
370 922920456008177641
371 980983941957467131
372 1042613756446266984
373 1108023767832688824
374 1177440365387220103
375 1251103179254532359
376 1329265832424796424
377 1412196743073267970
378 1500179962913990519
379 1593516071129547123
380 1692523108771735785
381 1797537574489903096
382 1908915465708409014
383 2027033387471716456
384 2152289712287169723
385 2285105814645263248
386 2425927362705733635
387 2575225692402041353
388 2733499245588629592
389 2901275099140258408
390 3079110565747582657
391 3267594895096611878
392 3467351055243620623
393 3679037624786888118
394 3903350774694247719
395 4141026372407647376
396 4392842186117903414
397 4659620223999393783
398 4942229185279697292
399 5241587060268098248
400 5558663855184076559
401 5894484481377277692
402 6250131783739451378
403 6626749750550389085
404 7025546878467532416
405 7447799737754661606
406 7894856710360827086
407 8368141948967203751
408 8869159528517598379
409 9399497841597817228
410 9960834208040697425
411 10554939753619315573
412 11183684527071123377
413 11849042914026141709
414 12553099315966884003
415 13298054156782895737
416 14086230183900558151
417 14920079130849051110
418 15802188707120794284
419 16735289986755899270
420 17722265160428726797
421 18766155727380831545
422 19870171090886467435
423 21037697638892129328
424 22272308272477670687
425 23577772469420922752
426 24958066844550885117
427 26417386300243630222
428 27960155727802284501
429 29591042359622817322
430 31314968732038818464
431 33137126365731259286
432 35062990122872370231
433 37098333355413241253
434 39249243803025223439
435 41522140363222398237
436 43923790691670353222
437 46461329763881965972
438 49142279355992666690
439 51974568585166227715
440 54966555467141940850
441 58127049641568110392
442 61465336222688534922
443 64991200936830042239
444 68714956504598830598
445 72647470440888077855
446 76800194231171278306
447 81185194069773209404
448 85815183119510792934
449 90703555491890498858
450 95864421908586654872
451 101312647257956435500
452 107063890009004762014
453 113134643712301975335
454 119542280552464032435
455 126305097198603651512
456 133442362920147088011
457 140974370232689238184
458 148922488044605146046
459 157309217588844231091
460 166158251114667873107
461 175494533644992735517
462 185344327778968290959
463 195735281868410488772
464 206696501553373114704
465 218258625010324943502
466 230453901904872444589
467 243316276429243196821
468 256881474424269926644
469 271187094995026872218
470 286272706628779467675
471 302179948255731800746
472 318952635271541463848
473 336636870995856792518
474 355281163597721304514
475 374936548998659497154
476 395656719797734461579
477 417498160768999010960
478 440520290990975211879
479 464785613201321975424
480 490359870453800331026
481 517312210716989432437
482 545715359511511043409
483 575645801275395119078
484 607183969576568572613
485 640414446916300182088
486 675426174267686559294
487 712312671151754440672
488 751172266423340577116
489 792108340633026494013
490 835229580168840098954
491 880650244112871658581
492 928490444051932116532
493 978876437852078377599
494 1031940937675584512227
495 1087823433331200638691
496 1146670531280385519320
497 1208636310478015765031
498 1273882695419530444131
499 1342579847668108612491
500 1414906576288545186876
501 1491050768564627249036
502 1571209841487594591621
503 1655591215504236063194
504 1744412811079994289059
505 1837903569686901039251
506 1936303999846779150559
507 2039866749971189457800
508 2148857208711870078305
509 2263554134705791076054
510 2384250316520987401871
511 2511253264842142118572
512 2644885937804184173030
513 2785487501681026374125
514 2933414127950721381418
515 3089039829126448485300
516 3252757334499640313355
517 3424979008382597721520
518 3606137812134772918762
519 3796688312775059269561
520 3997107739616522924045
521 4207897091959078079082
522 4429582299444612709142
523 4662715438363301731460
524 4907876005700635192562
525 5165672254488998843804
526 5436742592457259080019
527 5721757047840656626017
528 6021418804569137133870
529 6336465811020635728823
530 6667672464804417543950
531 7015851378113242617060
532 7381855226381201056596
533 7766578685168269872349
534 8170960458307338686302
535 8595985402650065530627
536 9042686752775447634860
537 9512148451448730877166
538 10005507589555055415258
539 10523956961785310944452
540 11068747742194561591392
541 11641192286442720929468
542 12242667065272028144958
543 12874615736609310826739
544 13538552361323985897510
545 14236064770657644557354
546 14968818090878744899103
547 15738558433860434635357
548 16547116759707450710219
549 17396412920871383872058
550 18288459894507591430819
551 19225368213317924372385
552 20209350602319894203462
553 21242726832660948209655
554 22327928800670675840745
555 23467505844219839615499
556 24664130305402537944301
557 25920603352642226558313
558 27239861072139224190764
559 28624980842881478361591
560 30079188006121720175804
561 31605862844760826530583
562 33208547884618391721357
563 34890955534353006221841
564 36656976077191883058083
565 38510686032669271162946
566 40456356902820990028960
567 42498464322595654604702
568 44641697630337081918061
569 46890969879793649815159
570 49251428311046485951233
571 51728465303653725062063
572 54327729831081098750087
573 57055139441716480548595
574 59916892787371279353795
575 62919482726738364972196
576 66069710026710069728817
577 69374697691385131626376
578 72841905943850751854670
579 76479147893131059424982
580 80294605913769602304914
581 84296848773219249196328
582 88494849537105013462848
583 92898004290554515472709
584 97516151708493950969021
585 102359593516385384265541
586 107439115877391471029570
587 112766011751005397226878
588 118352104262498772534452
589 124209771132092899757996
590 130351970206874404539715
591 136792266148560080597516
592 143544858324129010190869
593 150624609956985084816133
594 158047078590022628844811
595 165828547923206791135994
596 173986061081783445431583
597 182537455383102301029533
598 191501398663331983217582
599 200897427237880921609551
600 210745985562425435254946
601 221068467674686906164172
602 231887260489978924371342
603 243225789037534497763288
604 255108563717294478825344
605 267561229671619852328014
606 280610618358856732889611
607 294284801431304052333422
608 308613147012396861176335
609 323626378484430964668622
610 339356635890218004227729
611 355837540069517236748995
612 373104259642960762507771
613 391193580974647625918162
614 410143981236265172681610
615 429995704715118944155251
616 450790842499955793147505
617 472573415699115855608013
618 495389462336884453882183
619 519287128095763223637968
620 544316761063557774433304
621 570531010667300401885411
622 597984930967060819498785
623 626736088507169573598471
624 656844674913287936309912
625 688373624449664208191215
626 721388736741717780325161
627 755958804896524572641774
628 792155749244492926984344
629 830054756954571709492265
630 869734427765989046597211
631 911276926110295250470330
632 954768139888108442944670
633 1000297846197570240445225
634 1047959884302144412546873
635 1097852336159948920813778
636 1150077714827476838681391
637 1204743161087192079688194
638 1261960648639230167680549
639 1321847198236272960208625
640 1384525101131535998267682
641 1450122152250994412819359
642 1518771893492022986119275
643 1590613867594313475534892
644 1665793883020218110322144
645 1744464290328020841600187
646 1826784270513224389351131
647 1912920135842130616960475
648 2003045643693953544977560
649 2097342323979916037596815
650 2195999820700196196150391
651 2299216248255024800973513
652 2407198563119191689079690
653 2520162951548088158029331
654 2638335233977011480446498
655 2761951286837987764102113
656 2891257482512716870242974
657 3026511148206680490896410
658 3167981044524669628371225
659 3315947864598590398471828
660 3470704754614624659708983
661 3632557856661868396490869
662 3801826874821933235031433
663 3978845665498788397127394
664 4163962852986786663064862
665 4357542471359672405340635
666 4559964633763518186529383
667 4771626230286795457809272
668 4992941655582604729328452
669 5224343567514124445016483
670 5466283678098039069809795
671 5719233578122905621675587
672 5983685596825234752872126
673 6260153698114846618910625
674 6549174414849243505229919
675 6851307822772565681498038
676 7167138555745518922264027
677 7497276864016007361255658
678 7842359717293972991246684
679 8203051954525326824574795
680 8580047482276895959409533
681 8974070523784292673176346
682 9385876920735281227367048
683 9816255490010390290630984
684 10266029437627214944156597
685 10736057832293852863046765
686 11227237141006065360408616
687 11740502829292272330463700
688 12276831028744550987444813
689 12837240274654575009728287
690 13422793316612917716740831
691 14034599005122945014842082
692 14673814257325984524751559
693 15341646105140144556268088
694 16039353829167190128573187
695 16768251181941357803573516
696 17529708704153254796277930
697 18325156137716221255828321
698 19156084939609733029780881
699 20024050900684462911189090
700 20930676873689520828122765
701 21877655615049356054466647
702 22866752745003252798249360
703 23899809831005435172950993
704 24978747599379694681044689
705 26105569280526954418292356
706 27282364093091514339651398
707 28511310872817017415546697
708 29794681851943014057349766
709 31134846595340575322683074
710 32534276099718903780677575
711 33995547062606340761366850
712 35521346327957582778591963
713 37114475515635950684566281
714 38777855842184252214477011
715 40514533140722224270033445
716 42327683087990989973473861
717 44220616647018802548642825
718 46196785734084143800883133
719 48259789119137581733843446
720 50413378569066670051627708
721 52661465243707277301154055
722 55008126354750558758987706
723 57457612098250101145634892
724 60014352871704565839555995
725 62682966787285294345395854
726 65468267493076303035156297
727 68375272314829860054940707
728 71409210731068329781523440
729 74575533195043386305200203
730 77879920317423278492282997
731 81328292424307124819239458
732 84926819505559662055938601
733 88681931569239520235881302
734 92600329418326391155682250
735 96688995866787197651855729
736 100955207412494745321355431
737 105406546385406167356716906
738 110050913589926427646094138
739 114896541461339363670430425
740 119952007756755048133791281
741 125226249802047477858028248
742 130728579316875308926256388
743 136468697840976548046507042
744 142456712785603638952964424
745 148703154135141854866074916
746 155218991824690991087539470
747 162015653820650828661940564
748 169105044932154595528837375
749 176499566382545258069665159
750 184212136170965438587757212
751 192256210255579074159223871
752 200645804590897051822366314
753 209395518053230169734683205
754 218520556289331475782810246
755 228036756524952525510087688
756 237960613371168327800912239
757 248309305668107760221394049
758 259100724406955449891063121
759 270353501773001413056730374
760 282087041353851001657957053
761 294321549558955668000451831
762 307078068298077050108631233
763 320378508968492589504891204
764 334245687802327966927323023
765 348703362627755934056146437
766 363776271099513355338853169
767 379490170456712757921128024
768 395871878867782961159857872
769 412949318425080503208113142
770 430751559853729581000824280
771 449308869002151431027216109
772 468652755183930400956259476
773 488816021443777597476501719
774 509832816822723226142580820
775 531738690701008222209134762
776 554570649299714506654883686
777 578367214425755105353667750
778 603168484547628335291750825
779 629016198293182343708641605
780 655953800463650428774355731
781 684026510662338901200494118
782 713281394639612773040991573
783 743767438460245626092483591
784 775535625602732528902149878
785 808639017104907626639206238
786 843132834874030649960861038
787 879074548284594605949803054
788 916523964191242324664438036
789 955543320489638130632516431
790 996197383362613521841201930
791 1038553548354762045540262945
792 1082681945423494657406408776
793 1128655548120849995907749423
794 1176550287065581812666351821
795 1226445167871787059747593016
796 1278422393705988023878496099
797 1332567492651814792343555839
798 1388969450067538980280150541
799 1447720846129470156834742482
800 1508917998760820897814815050
801 1572661112153973137353790536
802 1639054431101200561551395685
803 1708206401357836164162498392
804 1780229836269564319608405279
805 1855242089905103161086928271
806 1933365236943845025447289347
807 2014726259578308894179703526
808 2099457241700219313793689154
809 2187695570650063281338116159
810 2279584146819646072787765819
811 2375271601409009656758530063
812 2474912522649509822672025132
813 2578667690817555313940393817
814 2686704322374765827157107809
815 2799196323583940448500405651
816 2916324553962365178816023234
817 3038277099948618097191711936
818 3165249559172118300696431856
819 3297445335730362412037676639
820 3435075946892902512878416116
821 3578361341667962535738853697
822 3727530231682800007551306413
823 3882820434846992141870249644
824 4044479232284217892117654906
825 4212763739037498077356412040
826 4387941289070520152126013832
827 4570289835108478953864366972
828 4760098363880896739448005925
829 4957667327351207651510232875
830 5163309090538393888850783647
831 5377348396559910001113616807
832 5600122849547214201838209971
833 5831983416110920184271541778
834 6073294946056364027317851435
835 6324436713077947465000657363
836 6585802976186225397798340084
837 6857803562651280102259583843
838 7140864473273492863134959250
839 7435428510824551707839195462
840 7741955932531209983329793295
841 8060925127508347802619378921
842 8392833320079828942516775869
843 8738197299962159574370994663
844 9097554180320328382187758944
845 9471462184744377026018456073
846 9860501464232236078264132234
847 10265274945306378508496307626
848 10686409210431635347627355533
849 11124555411946588373174177241
850 11580390220763761025028719906
851 12054616811142172581089311933
852 12547965882881863284401229712
853 13061196722341851655536468944
854 13595098303732502659509402124
855 14150490432188901672151576767
856 14728224930185077120641606260
857 15329186868908564649129003373
858 15954295846272058289651070342
859 16604507313302868097537620033
860 17280813950712454898583846561
861 17984247097516921794845208451
862 18715878233645506845975481628
863 19476820518547698408326740496
864 20268230387880710669186816323
865 21091309210437958787879631835
866 21947305007555602229356530747
867 22837514237318833685282800382
868 23763283645971721064223153235
869 24726012189025134908606934259
870 25727153024645540200581101864
871 26768215582004710623906088437
872 27850767707365231681428101927
873 28976437890780961649063467454
874 30146917576393466441925240767
875 31363963559417272862646878116
876 32629400473016181675343792481
877 33945123368392774036897307476
878 35313100391530739082237153023
879 36735375560158182172259409484
880 38214071644626251270633729589
881 39751393156535206700422140014
882 41349629449075549324723349743
883 43011157933199525997992035241
884 44738447413883805376468645872
885 46534061550902443490563639888
886 48400662448685437520943269347
887 50341014380007871128628157341
888 52357987648422309966597065625
889 54454562594528998784061369773
890 56633833751358368938977620130
891 58899014154335311992541741216
892 61253439811487818890303924275
893 63700574339771512017890735134
894 66244013773588874477050125842
895 68887491551805881518313325569
896 71634883689791162772157502869
897 74490214143242758761763480155
898 77457660370806190384606686583
899 80541559102744664725448357410
900 83746412323178288528303309778
901 87076893473684650201542210851
902 90537853886327814682231834615
903 94134329454477949908931610348
904 97871547550078452615802093996
905 101754934196333691042973517382
906 105790121505106520022644168459
907 109982955388653536846894454965
908 114339503555664996028792340513
909 118866063801939268417837365530
910 123569172606385221249150230029
911 128455614043434719392684539809
912 133532429023337224183757120712
913 138806924872224966589667162505
914 144286685264255097742800266025
915 149979580518581343856046286587
916 155893778274355764306286380573
917 162037754557439041158080900233
918 168420305252978080145178512539
919 175050557998521464450552978111
920 181937984512858217221593858557
921 189092413376313402621551421112
922 196524043278786014353349780146
923 204243456752401532311592265049
924 212261634406243063109130925143
925 220589969681253491222401574573
926 229240284144035010976132131889
927 238224843338945409453210074384
928 247556373218569808358783927867
929 257248077173367171845833864725
930 267313653682018812714288540255
931 277767314604777652331607136573
932 288623804142896916158933562152
933 299898418488042947749528546922
934 311607026186432401421465475328
935 323766089243318351389688800234
936 336392684994344985050804452341
937 349504528771237162216404566600
938 363119997390249975218225904545
939 377258153492816734494617468248
940 391938770768860838706383157420
941 407182360094321590441365552292
942 423010196615543999410422262195
943 439444347814343484272401487799
944 456507702588734403976740090874
945 474224001385553780603654000036
946 492617867422473076761533657675
947 511714839038220540460098099407
948 531541403211187428853829569330
949 552125030288014334877458803144
950 573494209965200151203877594595
951 595678488568298838612607175369
952 618708507674817628470066169169
953 642616044128559539639748251912
954 667434051494810799745578299992
955 693196703007516997931213127524
956 719939436061366332323930100315
957 747698998303563410322816359003
958 776513495381976519529835349748
959 806422440408336646568245543551
960 837466805197199554128424590068
961 869689073343516829458949843474
962 903133295203837663002757362440
963 937845144848446551710476231788
964 973871979054070647623822467511
965 1011262898409232981584344369257
966 1050068810606819538231129940855
967 1090342496001040676621560241297
968 1132138675508633612967438006784
969 1175514080936946886112157661343
970 1220527527824400444299126792048
971 1267239990881803349524721836908
972 1315714682126063144886300659807
973 1366017131801016753195850386189
974 1418215272183377860292544363520
975 1472379524375213236219249363683
976 1528582888187853201441354420848
977 1586901035225795793309457984978
978 1647412405282900233563517426744
979 1710198306167072689497383360654
980 1775343017073643336583366185159
981 1842933895631811453804713489954
982 1913061488752809071755500576553
983 1985819647412900200775286193955
984 2061305645508903233902915455445
985 2139620302928699104719647268413
986 2220868112984075411620589664061
987 2305157374358361202454717882865
988 2392600327726533459862718909587
989 2483313297210932738065266613829
990 2577416836841313570537705698753
991 2675035882193787543344658676805
992 2776299907389191579463906347882
993 2881343087637647662340293486435
994 2990304467522467674492079798500
995 3103328135223219371355961848293
996 3220563402884597835509573209297
997 3342164993344866841014093752599
998 3468293233444933721370932452698
999 3599114254146730183706022089007
1000 3734800197697373481707622358878