3 1
4 2
5 5
6 13
7 33
8 79
9 176
10 365
11 709
12 1300
13 2267
14 3785
15 6085
16 9465
17 14302
18 21065
19 30329
20 42790
21 59281
22 80789
23 108473
24 143683
25 187980
26 243157
27 311261
28 394616
29 495847
30 617905
31 764093
32 938093
33 1143994
34 1386321
35 1670065
36 2000714
37 2384285
38 2827357
39 3337105
40 3921335
41 4588520
42 5347837
43 6209205
44 7183324
45 8281715
46 9516761
47 10901749
48 12450913
49 14179478
50 16103705
51 18240937
52 20609646
53 23229481
54 26121317
55 29307305
56 32810923
57 36657028
58 40871909
59 45483341
60 50520640
61 56014719
62 61998145
63 68505197
64 75571925
65 83236210
66 91537825
67 100518497
68 110221970
69 120694069
70 131982765
71 144138241
72 157212959
73 171261728
74 186341773
75 202512805
76 219837092
77 238379531
78 258207721
79 279392037
80 302005705
81 326124878
82 351828713
83 379199449
84 408322486
85 439286465
86 472183349
87 507108505
88 544160787
89 583442620
90 625060085
91 669123005
92 715745032
93 765043735
94 817140689
95 872161565
96 930236221
97 991498794
98 1056087793
99 1124146193
100 1195821530
101 1271265997
102 1350636541
103 1434094961
104 1521808007
105 1613947480
106 1710690333
107 1812218773
108 1918720364
109 2030388131
110 2147420665
111 2270022229
112 2398402865
113 2532778502
114 2673371065
115 2820408585
116 2974125310
117 3134761817
118 3302565125
119 3477788809
120 3660693115
121 3851545076
122 4050618629
123 4258194733
124 4474561488
125 4700014255
126 4934855777
127 5179396301
128 5433953701
129 5698853602
130 5974429505
131 6261022913
132 6558983458
133 6868669029
134 7190445901
135 7524688865
136 7871781359
137 8232115600
138 8606092717
139 8994122885
140 9396625460
141 9814029115
142 10246771977
143 10695301765
144 11160075929
145 11641561790
146 12140236681
147 12656588089
148 13191113798
149 13744322033
150 14316731605
151 14908872057
152 15521283811
153 16154518316
154 16809138197
155 17485717405
156 18184841368
157 18907107143
158 19653123569
159 20423511421
160 21218903565
161 22039945114
162 22887293585
163 23761619057
164 24663604330
165 25593945085
166 26553350045
167 27542541137
168 28562253655
169 29613236424
170 30696251965
171 31812076661
172 32961500924
173 34145329363
174 35364380953
175 36619489205
176 37911502337
177 39241283446
178 40609710681
179 42017677417
180 43466092430
181 44955880073
182 46487980453
183 48063349609
184 49682959691
185 51347799140
186 53058872869
187 54817202445
188 56623826272
189 58479799775
190 60386195585
191 62344103725
192 64354631797
193 66418905170
194 68538067169
195 70713279265
196 72945721266
197 75236591509
198 77587107053
199 79998503873
200 82472037055
201 85008980992
202 87610629581
203 90278296421
204 93013315012
205 95817038955
206 98690842153
207 101636119013
208 104654284649
209 107746775086
210 110915047465
211 114160580249
212 117484873430
213 120889448737
214 124375849845
215 127945642585
216 131600415155
217 135341778332
218 139171365685
219 143090833789
220 147101862440
221 151206154871
222 155405437969
223 159701462493
224 164096003293
225 168590859530
226 173187854897
227 177888837841
228 182695681786
229 187610285357
230 192634572605
231 197770493233
232 203020022823
233 208385163064
234 213867941981
235 219470414165
236 225194661004
237 231042790915
238 237016939577
239 243119270165
240 249351973585
241 255717268710
242 262217402617
243 268854650825
244 275631317534
245 282549735865
246 289612268101
247 296821305929
248 304179270683
249 311688613588
250 319351816005
251 327171389677
252 335149876976
253 343289851151
254 351593916577
255 360064709005
256 368704895813
257 377517176258
258 386504281729
259 395668976001
260 405014055490
261 414542349509
262 424256720525
263 434160064417
264 444255310735
265 454545422960
266 465033398765
267 475722270277
268 486615104340
269 497715002779
270 509025102665
271 520548576581
272 532288632889
273 544248515998
274 556431506633
275 568840922105
276 581480116582
277 594352481361
278 607461445141
279 620810474297
280 634403073155
281 648242784268
282 662333188693
283 676677906269
284 691280595896
285 706144955815
286 721274723889
287 736673677885
288 752345635757
289 768294455930
290 784524037585
291 801038320945
292 817841287562
293 834936960605
294 852329405149
295 870022728465
296 888021080311
297 906328653224
298 924949682813
299 943888448053
300 963149271580
301 982736519987
302 1002654604121
303 1022907979381
304 1043501146017
305 1064438649430
306 1085725080473
307 1107365075753
308 1129363317934
309 1151724536041
310 1174453505765
311 1197555049769
312 1221034037995
313 1244895387972
314 1269144065125
315 1293785083085
316 1318823504000
317 1344264438847
318 1370113047745
319 1396374540269
320 1423054175765
321 1450157263666
322 1477689163809
323 1505655286753
324 1534061094098
325 1562912098805
326 1592213865517
327 1621972010881
328 1652192203871
329 1682880166112
330 1714041672205
331 1745682550053
332 1777808681188
333 1810426001099
334 1843540499561
335 1877158220965
336 1911285264649
337 1945927785230
338 1981091992937
339 2016784153945
340 2053010590710
341 2089777682305
342 2127091864757
343 2164959631385
344 2203387533139
345 2242382178940
346 2281950236021
347 2322098430269
348 2362833546568
349 2404162429143
350 2446091981905
351 2488629168797
352 2531781014141
353 2575554602986
354 2619957081457
355 2664995657105
356 2710677599258
357 2757010239373
358 2804000971389
359 2851657252081
360 2899986601415
361 2948996602904
362 2998694903965
363 3049089216277
364 3100187316140
365 3151997044835
366 3204526308985
367 3257783080917
368 3311775399025
369 3366511368134
370 3421999159865
371 3478247013001
372 3535263233854
373 3593056196633
374 3651634343813
375 3711006186505
376 3771180304827
377 3832165348276
378 3893970036101
379 3956603157677
380 4020073572880
381 4084390212463
382 4149562078433
383 4215598244429
384 4282507856101
385 4350300131490
386 4418984361409
387 4488569909825
388 4559066214242
389 4630482786085
390 4702829211085
391 4776115149665
392 4850350337327
393 4925544585040
394 5001707779629
395 5078849884165
396 5156980938356
397 5236111058939
398 5316250440073
399 5397409353733
400 5479598150105
401 5562827257982
402 5647107185161
403 5732448518841
404 5818861926022
405 5906358153905
406 5994948030293
407 6084642463993
408 6175452445219
409 6267389045996
410 6360463420565
411 6454686805789
412 6550070521560
413 6646625971207
414 6744364641905
415 6843298105085
416 6943438016845
417 7044796118362
418 7147384236305
419 7251214283249
420 7356298258090
421 7462648246461
422 7570276421149
423 7679195042513
424 7789416458903
425 7900953107080
426 8013817512637
427 8128022290421
428 8243580144956
429 8360503870867
430 8478806353305
431 8598500568373
432 8719599583553
433 8842116558134
434 8966064743641
435 9091457484265
436 9218308217294
437 9346630473545
438 9476437877797
439 9607744149225
440 9740563101835
441 9874908644900
442 10010794783397
443 10148235618445
444 10287245347744
445 10427838266015
446 10570028765441
447 10713831336109
448 10859260566453
449 11006331143698
450 11155057854305
451 11305455584417
452 11457539320306
453 11611324148821
454 11766825257837
455 11924057936705
456 12083037576703
457 12243779671488
458 12406299817549
459 12570613714661
460 12736737166340
461 12904686080299
462 13074476468905
463 13246124449637
464 13419646245545
465 13595058185710
466 13772376705705
467 13951618348057
468 14132799762710
469 14315937707489
470 14501049048565
471 14688150760921
472 14877259928819
473 15068393746268
474 15261569517493
475 15456804657405
476 15654116692072
477 15853523259191
478 16055042108561
479 16258691102557
480 16464488216605
481 16672451539658
482 16882599274673
483 17094949739089
484 17309521365306
485 17526332701165
486 17745402410429
487 17966749273265
488 18190392186727
489 18416350165240
490 18644642341085
491 18875287964885
492 19108306406092
493 19343717153475
494 19581539815609
495 19821794121365
496 20064499920401
497 20309677183654
498 20557346003833
499 20807526595913
500 21060239297630
501 21315504569977
502 21573342997701
503 21833775289801
504 22096822280027
505 22362504927380
506 22630844316613
507 22901861658733
508 23175578291504
509 23452015679951
510 23731195416865
511 24013139223309
512 24297868949125
513 24585406573442
514 24875774205185
515 25168994083585
516 25465088578690
517 25764080191877
518 26065991556365
519 26370845437729
520 26678664734415
521 26989472478256
522 27303291834989
523 27620146104773
524 27940058722708
525 28263053259355
526 28589153421257
527 28918383051461
528 29250766130041
529 29586326774622
530 29925089240905
531 30267077923193
532 30612317354918
533 30960832209169
534 31312647299221
535 31667787579065
536 32026278143939
537 32388144230860
538 32753411219157
539 33122104631005
540 33494250131960
541 33869873531495
542 34249000783537
543 34631657987005
544 35017871386349
545 35407667372090
546 35801072481361
547 36198113398449
548 36598816955338
549 37003210132253
550 37411320058205
551 37823174011537
552 38238799420471
553 38658223863656
554 39081475070717
555 39508580922805
556 39939569453148
557 40374468847603
558 40813307445209
559 41256113738741
560 41702916375265
561 42153744156694
562 42608626040345
563 43067591139497
564 43530668723950
565 43997888220585
566 44469279213925
567 44944871446697
568 45424694820395
569 45908779395844
570 46397155393765
571 46889853195341
572 47386903342784
573 47888336539903
574 48394183652673
575 48904475709805
576 49419243903317
577 49938519589106
578 50462334287521
579 50990719683937
580 51523707629330
581 52061330140853
582 52603619402413
583 53150607765249
584 53702327748511
585 54258812039840
586 54820093495949
587 55386205143205
588 55957180178212
589 56533051968395
590 57113854052585
591 57699620141605
592 58290384118857
593 58886180040910
594 59487042138089
595 60093004815065
596 60704102651446
597 61320370402369
598 61941842999093
599 62568555549593
600 63200543339155
601 63837841830972
602 64480486666741
603 65128513667261
604 65781958833032
605 66440858344855
606 67105248564433
607 67775166034973
608 68450647481789
609 69131729812906
610 69818450119665
611 70510845677329
612 71208953945690
613 71912812569677
614 72622459379965
615 73337932393585
616 74059269814535
617 74786510034392
618 75519691632925
619 76258853378709
620 77004034229740
621 77755273334051
622 78512610030329
623 79276083848533
624 80045734510513
625 80821601930630
626 81603726216377
627 82392147669001
628 83186906784126
629 83988044252377
630 84795600960005
631 85609617989513
632 86430136620283
633 87257198329204
634 88090844791301
635 88931117880365
636 89778059669584
637 90631712432175
638 91492118642017
639 92359320974285
640 93233362306085
641 94114285717090
642 95002134490177
643 95896952112065
644 96798782273954
645 97707668872165
646 98623656008781
647 99546787992289
648 100477109338223
649 101414664769808
650 102359499218605
651 103311657825157
652 104271185939636
653 105238129122491
654 106212533145097
655 107194443990405
656 108183907853593
657 109180971142718
658 110185680479369
659 111198082699321
660 112218224853190
661 113246154207089
662 114281918243285
663 115325564660857
664 116377141376355
665 117436696524460
666 118504278458645
667 119579935751837
668 120663717197080
669 121755671808199
670 122855848820465
671 123964297691261
672 125081068100749
673 126206209952538
674 127339773374353
675 128481808718705
676 129632366563562
677 130791497713021
678 131959253197981
679 133135684276817
680 134320842436055
681 135514779391048
682 136717547086653
683 137929197697909
684 139149783630716
685 140379357522515
686 141617972242969
687 142865680894645
688 144122536813697
689 145388593570550
690 146663904970585
691 147948525054825
692 149242508100622
693 150545908622345
694 151858781372069
695 153181181340265
696 154513163756491
697 155854784090084
698 157206098050853
699 158567161589773
700 159938030899680
701 161318762415967
702 162709412817281
703 164110039026221
704 165520698210037
705 166941447781330
706 168372345398753
707 169813448967713
708 171264816641074
709 172726506819861
710 174198578153965
711 175681089542849
712 177174100136255
713 178677669334912
714 180191856791245
715 181716722410085
716 183252326349380
717 184798729020907
718 186355991090985
719 187924173481189
720 189503337369065
721 191093544188846
722 192694855632169
723 194307333648793
724 195931040447318
725 197566038495905
726 199212390522997
727 200870159518041
728 202539408732211
729 204220201679132
730 205912602135605
731 207616674142333
732 209332482004648
733 211060090293239
734 212799563844881
735 214550967763165
736 216314367419229
737 218089828452490
738 219877416771377
739 221677198554065
740 223489240249210
741 225313608576685
742 227150370528317
743 228999593368625
744 230861344635559
745 232735692141240
746 234622703972701
747 236522448492629
748 238434994340108
749 240360410431363
750 242298765960505
751 244250130400277
752 246214573502801
753 248192165300326
754 250182976105977
755 252187076514505
756 254204537403038
757 256235429931833
758 258279825545029
759 260337795971401
760 262409413225115
761 264494749606484
762 266593877702725
763 268706870388717
764 270833800827760
765 272974742472335
766 275129769064865
767 277298954638477
768 279482373517765
769 281680100319554
770 283892209953665
771 286118777623681
772 288359878827714
773 290615589359173
774 292885985307533
775 295171143059105
776 297471139297807
777 299786051005936
778 302115955464941
779 304460930256197
780 306821053261780
781 309196402665243
782 311587056952393
783 313993094912069
784 316414595636921
785 318851638524190
786 321304303276489
787 323772669902585
788 326256818718182
789 328756830346705
790 331272785720085
791 333804766079545
792 336352852976387
793 338917128272780
794 341497674142549
795 344094573071965
796 346707907860536
797 349337761621799
798 351984217784113
799 354647360091453
800 357327272604205
801 360024039699962
802 362737746074321
803 365468476741681
804 368216317036042
805 370981352611805
806 373763669444573
807 376563353831953
808 379380492394359
809 382215172075816
810 385067480144765
811 387937504194869
812 390825332145820
813 393731052244147
814 396654753064025
815 399596523508085
816 402556452808225
817 405534630526422
818 408531146555545
819 411546091120169
820 414579554777390
821 417631628417641
822 420702403265509
823 423791970880553
824 426900423158123
825 430027852330180
826 433174350966117
827 436340011973581
828 439524928599296
829 442729194429887
830 445952903392705
831 449196149756653
832 452459028133013
833 455741633476274
834 459044061084961
835 462366406602465
836 465708766017874
837 469071235666805
838 472453912232237
839 475856892745345
840 479280274586335
841 482724155485280
842 486188633522957
843 489673807131685
844 493179775096164
845 496706636554315
846 500254490998121
847 503823438274469
848 507413578585993
849 511025012491918
850 514657840908905
851 518312165111897
852 521988086734966
853 525685707772161
854 529405130578357
855 533146457870105
856 536909792726483
857 540695238589948
858 544502899267189
859 548332878929981
860 552185282116040
861 556060213729879
862 559957779043665
863 563878083698077
864 567821233703165
865 571787335439210
866 575776495657585
867 579788821481617
868 583824420407450
869 587883400304909
870 591965869418365
871 596071936367601
872 600201710148679
873 604355300134808
874 608532816077213
875 612734368106005
876 616960066731052
877 621210022842851
878 625484347713401
879 629783152997077
880 634106550731505
881 638454653338438
882 642827573624633
883 647225424782729
884 651648320392126
885 656096374419865
886 660569701221509
887 665068415542025
888 669592632516667
889 674142467671860
890 678718036926085
891 683319456590765
892 687946843371152
893 692600314367215
894 697279987074529
895 701985979385165
896 706718409588581
897 711477396372514
898 716263058823873
899 721075516429633
900 725914889077730
901 730781297057957
902 735674861062861
903 740595702188641
904 745543941936047
905 750519702211280
906 755523105326893
907 760554274002693
908 765613331366644
909 770700400955771
910 775815606717065
911 780959073008389
912 786130924599385
913 791331286672382
914 796560284823305
915 801818045062585
916 807104693816070
917 812420357925937
918 817765164651605
919 823139241670649
920 828542717079715
921 833975719395436
922 839438377555349
923 844930820918813
924 850453179267928
925 856005582808455
926 861588162170737
927 867201048410621
928 872844373010381
929 878518267879642
930 884222865356305
931 889958298207473
932 895724699630378
933 901522203253309
934 907350943136541
935 913211053773265
936 919102670090519
937 925025927450120
938 930980961649597
939 936967908923125
940 942986905942460
941 949038089817875
942 955121598099097
943 961237568776245
944 967386140280769
945 973567451486390
946 979781641710041
947 986028850712809
948 992309218700878
949 998622886326473
950 1004969994688805
951 1011350685335017
952 1017765100261131
953 1024213381912996
954 1030695673187237
955 1037212117432205
956 1043762858448928
957 1050348040492063
958 1056967808270849
959 1063622306950061
960 1070311682150965
961 1077036079952274
962 1083795646891105
963 1090590529963937
964 1097420876627570
965 1104286834800085
966 1111188552861805
967 1118126179656257
968 1125099864491135
969 1132109757139264
970 1139156007839565
971 1146238767298021
972 1153358186688644
973 1160514417654443
974 1167707612308393
975 1174937923234405
976 1182205503488297
977 1189510506598766
978 1196853086568361
979 1204233397874457
980 1211651595470230
981 1219107834785633
982 1226602271728373
983 1234135062684889
984 1241706364521331
985 1249316334584540
986 1256965130703029
987 1264652911187965
988 1272379834834152
989 1280146060921015
990 1287951749213585
991 1295797059963485
992 1303682153909917
993 1311607192280650
994 1319572336793009
995 1327577749654865
996 1335623593565626
997 1343710031717229
998 1351837227795133
999 1360005345979313
1000 1368214550945255