1 0
2 0
3 0
4 2
5 10
6 30
7 86
8 180
9 344
10 624
11 1056
12 1626
13 2522
14 3646
15 5118
16 7164
17 9784
18 12868
19 16848
20 21438
21 27202
22 34298
23 42550
24 51800
25 63184
26 76256
27 91032
28 108086
29 127850
30 149442
31 174902
32 202552
33 233608
34 268512
35 306664
36 349394
37 398226
38 450510
39 507038
40 569204
41 638752
42 712644
43 795008
44 882246
45 977202
46 1082142
47 1193910
48 1311628
49 1441488
50 1579808
51 1728736
52 1888306
53 2059370
54 2238430
55 2431750
56 2638276
57 2860952
58 3097548
59 3345896
60 3604542
61 3886746
62 4180330
63 4487334
64 4815700
65 5162992
66 5529692
67 5920216
68 6324966
69 6750794
70 7197746
71 7672878
72 8164224
73 8689832
74 9232904
75 9796320
76 10391186
77 11013226
78 11664078
79 12349454
80 13055676
81 13802088
82 14581884
83 15387840
84 16216918
85 17096114
86 18011146
87 18955254
88 19935048
89 20959360
90 22010992
91 23121768
92 24274986
93 25470418
94 26707766
95 27980710
96 29299172
97 30681504
98 32097628
99 33563336
100 35088490
101 36677362
102 38303494
103 39992254
104 41719644
105 43511520
106 45383636
107 47303088
108 49264678
109 51310418
110 53400242
111 55567294
112 57796312
113 60111264
114 62474312
115 64917232
116 67430378
117 70013914
118 72683666
119 75413246
120 78219392
121 81153320
122 84156532
123 87224808
124 90371190
125 93599242
126 96909602
127 100345638
128 103844856
129 107441048
130 111123968
131 114919000
132 118781346
133 122779874
134 126877446
135 131055006
136 135367128
137 139797336
138 144302752
139 148930128
140 153634586
141 158499898
142 163471510
143 168534206
144 173713268
145 179070040
146 184545436
147 190118368
148 195834186
149 201671642
150 207599494
151 213709542
152 219912988
153 226265880
154 232774360
155 239448160
156 246258994
157 253267146
158 260378678
159 267606382
160 274971892
161 282541688
162 290262740
163 298173424
164 306195982
165 314370578
166 322761530
167 331282534
168 339920472
169 348825616
170 357876512
171 367129944
172 376583054
173 386206346
174 395957322
175 405910598
176 416081728
177 426486712
178 437068248
179 447801928
180 458672618
181 469874322
182 481218006
183 492800078
184 504571340
185 516570928
186 528772620
187 541209056
188 553857918
189 566712818
190 579851910
191 593250150
192 606809028
193 620684512
194 634724604
195 648948504
196 663483158
197 678300954
198 693290538
199 708618302
200 724121960
201 739963912
202 756039352
203 772316544
204 788844770
205 805724170
206 822857366
207 840201022
208 857845928
209 875826656
210 894079088
211 912790304
212 931704466
213 950888762
214 970338294
215 990017302
216 1009976652
217 1030381080
218 1051078308
219 1072015128
220 1093232294
221 1114881754
222 1136839426
223 1159143062
224 1181673864
225 1204635224
226 1228036164
227 1251698400
228 1275597294
229 1299943058
230 1324530034
231 1349507622
232 1374940536
233 1400753728
234 1426818400
235 1453369128
236 1480263450
237 1507498914
238 1535069126
239 1563067798
240 1591331620
241 1620239072
242 1649418876
243 1678973992
244 1708943262
245 1739278842
246 1770068974
247 1801291398
248 1832907284
249 1864961784
250 1897389628
251 1930274600
252 1963455502
253 1997328058
254 2031615970
255 2066241558
256 2101424408
257 2137083736
258 2173056984
259 2209508984
260 2246391210
261 2283894978
262 2321901378
263 2360270166
264 2398968064
265 2438379168
266 2478237272
267 2518642536
268 2559484258
269 2600776610
270 2642414790
271 2684811142
272 2727560452
273 2770911504
274 2814917220
275 2859323000
276 2904318430
277 2949990426
278 2996034850
279 3042490894
280 3089524468
281 3137398624
282 3185657444
283 3234498016
284 3283727142
285 3333465506
286 3383909786
287 3434998638
288 3486626544
289 3539131136
290 3592120160
291 3645758992
292 3699925714
293 3754636938
294 3809767966
295 3865692934
296 3922181732
297 3979314152
298 4037209808
299 4095586832
300 4154560938
301 4214535210
302 4275111062
303 4336183998
304 4397831620
305 4460245640
306 4523266588
307 4587154960
308 4651511302
309 4716775186
310 4782640818
311 4849256246
312 4916352896
313 4984472096
314 5053080648
315 5122228472
316 5192446998
317 5263313514
318 5334681698
319 5406802422
320 5479608968
321 5553409384
322 5627862352
323 5703141704
324 5779130642
325 5856156082
326 5934032926
327 6012499710
328 6091646724
329 6171598880
330 6252278092
331 6334172496
332 6416622814
333 6499794034
334 6583815238
335 6668455558
336 6753838484
337 6840560176
338 6927859116
339 7015939976
340 7104754598
341 7194675258
342 7285391970
343 7377210446
344 7469815148
345 7563313952
346 7657883172
347 7753125104
348 7848981270
349 7945946562
350 8043533122
351 8142326670
352 8242216900
353 8343264232
354 8444953468
355 8547595744
356 8651084742
357 8755412514
358 8860906946
359 8967124470
360 9074002432
361 9182584832
362 9291958244
363 9402072592
364 9513221498
365 9625671178
366 9739021246
367 9853395278
368 9968465676
369 10084692712
370 10201980192
371 10320364920
372 10439694722
373 10560305570
374 10681638766
375 10804125950
376 10927860308
377 11052677856
378 11178489204
379 11305885184
380 11434033334
381 11563589922
382 11694100090
383 11825446542
384 11957557840
385 12091176640
386 12226222760
387 12362124960
388 12499203950
389 12637295522
390 12776178114
391 12916794086
392 13058488912
393 13201652224
394 13345834224
395 13490909992
396 13637051210
397 13785024354
398 13933829454
399 14083546502
400 14234742692
401 14387633488
402 14541375132
403 14696369192
404 14852511270
405 15009757050
406 15168624786
407 15328857774
408 15490262464
409 15653483688
410 15817595768
411 15983079088
412 16149684226
413 16317442874
414 16486393774
415 16657001326
416 16828797484
417 17002248664
418 17176857516
419 17352936752
420 17529951398
421 17709434994
422 17889870202
423 18071346902
424 18254248636
425 18438553672
426 18624376524
427 18811620088
428 19000148046
429 19189928730
430 19381454066
431 19574497878
432 19768538008
433 19964794856
434 20162060984
435 20360902312
436 20561500986
437 20763407330
438 20966688670
439 21171477438
440 21377302756
441 21585350944
442 21795295180
443 22006906144
444 22219581038
445 22434128898
446 22650064394
447 22867175998
448 23085631840
449 23306163872
450 23527787328
451 23751846448
452 23977373074
453 24204313994
454 24432640710
455 24662186582
456 24893771676
457 25127657048
458 25362680460
459 25598947704
460 25837165242
461 26077498002
462 26318988766
463 26563003542
464 26808189932
465 27055284208
466 27304406332
467 27554825000
468 27806433494
469 28060657786
470 28316458930
471 28574099534
472 28833249504
473 29094167912
474 29356708560
475 29621034624
476 29887288378
477 30155854714
478 30426270634
479 30698056630
480 30971100368
481 31247254648
482 31525101264
483 31804343480
484 32085817658
485 32369320722
486 32654495014
487 32941920206
488 33230655404
489 33521290560
490 33813560644
491 34108316112
492 34404402358
493 34702814290
494 35003010530
495 35305316958
496 35610456956
497 35917803992
498 36226943356
499 36538076240
500 36850592566
501 37165573634
502 37482282738
503 37800515542
504 38120148048
505 38443307472
506 38768291016
507 39095495864
508 39424839266
509 39756004834
510 40088611046
511 40424288102
512 40761863796
513 41101689904
514 41443998648
515 41787915456
516 42133732154
517 42482125178
518 42832487470
519 43185154342
520 43539683412
521 43897391464
522 44256620900
523 44618571672
524 44982055062
525 45347482394
526 45716121306
527 46086450134
528 46458840480
529 46834762056
530 47212515148
531 47592650128
532 47975113786
533 48360514378
534 48748030966
535 49137863446
536 49529764956
537 49923995816
538 50320234916
539 50718247128
540 51118818234
541 51523458146
542 51929755550
543 52337858406
544 52748014396
545 53161111632
546 53576356612
547 53995205848
548 54415749902
549 54838438666
550 55263623342
551 55692017702
552 56122688612
553 56556813368
554 56993195452
555 57431473688
556 57872708862
557 58316160778
558 58761371834
559 59209715142
560 59660395104
561 60115221896
562 60573162664
563 61033066152
564 61494776682
565 61959603970
566 62426757830
567 62895895118
568 63368410148
569 63843561872
570 64320557892
571 64801442528
572 65284188022
573 65770386642
574 66258896490
575 66750278926
576 67244572576
577 67743037104
578 68243413248
579 68746314640
580 69251580386
581 69760314298
582 70271556038
583 70785579158
584 71302156860
585 71821531080
586 72344951112
587 72870516672
588 73398058402
589 73929850154
590 74464274110
591 75001695598
592 75541589340
593 76084698184
594 76629827972
595 77179137408
596 77732079822
597 78287602930
598 78845654858
599 79406894758
600 79970202152
601 80538589440
602 81109066624
603 81682729352
604 82259452366
605 82838827882
606 83421444326
607 84007094542
608 84594872532
609 85186381368
610 85781551076
611 86379939984
612 86981165710
613 87587022962
614 88195063202
615 88805476150
616 89419566432
617 90038278064
618 90659204168
619 91283295816
620 91909610530
621 92539918514
622 93173961106
623 93810444910
624 94449838968
625 95094269440
626 95741837400
627 96391882784
628 97045867682
629 97702738026
630 98362636046
631 99028505030
632 99696705092
633 100368227800
634 101042623756
635 101719565160
636 102399495662
637 103083444922
638 103771069430
639 104462346158
640 105157085096
641 105856517024
642 106558355352
643 107263626608
644 107971313194
645 108683400906
646 109399559598
647 110119488310
648 110841868132
649 111569509656
650 112300377324
651 113035842216
652 113775537926
653 114518372506
654 115263715458
655 116012632118
656 116764749528
657 117520870376
658 118280665860
659 119044312272
660 119810509422
661 120583172370
662 121358412338
663 122136449766
664 122918930176
665 123705097664
666 124495867552
667 125291213416
668 126090011290
669 126892110546
670 127697445030
671 128506712678
672 129319441204
673 130138604896
674 130960451756
675 131785210264
676 132615307106
677 133449572642
678 134286552382
679 135127391438
680 135971738644
681 136821708496
682 137675043708
683 138532595584
684 139392910286
685 140259081666
686 141128784090
687 142002625678
688 142879894160
689 143761595968
690 144646974512
691 145538185376
692 146432235762
693 147329843258
694 148233319026
695 149139900798
696 150050120016
697 150965978472
698 151885622648
699 152808407936
700 153734744050
701 154667503994
702 155603190790
703 156544848526
704 157490366884
705 158441393080
706 159397351316
707 160356540688
708 161319565598
709 162287648978
710 163258736370
711 164234277398
712 165214170996
713 166198346568
714 167186498316
715 168181019976
716 169180963982
717 170184748538
718 171192297010
719 172203187910
720 173217166344
721 174239485576
722 175265809264
723 176296223160
724 177330465666
725 178368630146
726 179411578398
727 180460084638
728 181511759668
729 182570022800
730 183633075784
731 184700860744
732 185772841314
733 186850249986
734 187930889462
735 189015030582
736 190105735192
737 191202057608
738 192302624512
739 193408879576
740 194518424914
741 195633790738
742 196754799414
743 197880797054
744 199010126060
745 200145952448
746 201286014588
747 202429712512
748 203578247970
749 204732910314
750 205891914014
751 207057695886
752 208226889932
753 209401447496
754 210580185580
755 211764163040
756 212952490998
757 214149221650
758 215349428362
759 216553399926
760 217763293376
761 218980310416
762 220200842968
763 221426338040
764 222656350674
765 223890769378
766 225132338034
767 226377759342
768 227627813432
769 228884888096
770 230145551656
771 231414011504
772 232686876666
773 233964252874
774 235245254630
775 236532538950
776 237825342828
777 239123295560
778 240427397636
779 241735479448
780 243048366102
781 244370454938
782 245697357258
783 247029945590
784 248368665756
785 249714614544
786 251065314564
787 252421328376
788 253781127182
789 255145641594
790 256514777818
791 257889507326
792 259269111880
793 260657965192
794 262051808464
795 263449819456
796 264854185514
797 266263369402
798 267676429438
799 269097544814
800 270523739484
801 271958078024
802 273398046144
803 274842276360
804 276291609474
805 277747563122
806 279210433078
807 280679355278
808 282153138732
809 283632543712
810 285115958220
811 286608252624
812 288104583774
813 289608127890
814 291116607794
815 292631243086
816 294151010632
817 295679669888
818 297213672864
819 298752123472
820 300298949766
821 301853025234
822 303411256202
823 304975326918
824 306543564584
825 308117657536
826 309700209448
827 311289032120
828 312882067202
829 314483874706
830 316089919894
831 317702186246
832 319319622756
833 320944920416
834 322576768168
835 324214636224
836 325857913882
837 327508955850
838 329167062898
839 330829859038
840 332496996496
841 334176561832
842 335861171160
843 337550522864
844 339245212226
845 340945364970
846 342652157942
847 344366543918
848 346087689224
849 347815763952
850 349549257712
851 351290890608
852 353038358914
853 354793318762
854 356552786654
855 358318977910
856 360094219352
857 361875826112
858 363661987712
859 365457635384
860 367257864250
861 369066099890
862 370881994518
863 372702877078
864 374528379492
865 376364491008
866 378206446476
867 380053435112
868 381907198806
869 383769268730
870 385637388962
871 387515023902
872 389398765024
873 391289127160
874 393186250612
875 395090590168
876 397003007062
877 398923377930
878 400848547634
879 402778903366
880 404715092200
881 406662154424
882 408614056424
883 410576259544
884 412543330666
885 414519162866
886 416502985118
887 418492104718
888 420486132708
889 422489593840
890 424499334428
891 426516295056
892 428542186982
893 430574241410
894 432612756762
895 434658250238
896 436710018928
897 438771507488
898 440841469176
899 442916879344
900 444998852058
901 447093704298
902 449195152998
903 451304280422
904 453421889972
905 455546662984
906 457677885060
907 459816302504
908 461959881318
909 464109857274
910 466267193694
911 468435641790
912 470609299564
913 472794203064
914 474985846892
915 477183156528
916 479389033798
917 481601434946
918 483820545090
919 486050206582
920 488285176240
921 490530805344
922 492782899248
923 495040759976
924 497305520170
925 499583609106
926 501869772958
927 504161769302
928 506461451008
929 508770333208
930 511084652640
931 513409921144
932 515743509222
933 518083876122
934 520430888546
935 522783830094
936 525146361136
937 527522064152
938 529903317704
939 532292797024
940 534689016370
941 537094904058
942 539506383542
943 541925667550
944 544352219684
945 546787467736
946 549235530392
947 551692090472
948 554154325418
949 556625953522
950 559104919254
951 561594197678
952 564090405068
953 566598260496
954 569111873964
955 571635293168
956 574165945790
957 576703753202
958 579251260050
959 581805038366
960 584366201448
961 586941964752
962 589524458020
963 592115781480
964 594715446754
965 597322398178
966 599936737710
967 602563146526
968 605195493588
969 607838050768
970 610490614796
971 613151867088
972 615819110798
973 618498187970
974 621184899026
975 623878112270
976 626583391208
977 629298024400
978 632018731416
979 634747897568
980 637484877738
981 640234954058
982 642993709170
983 645759085710
984 648530605440
985 651313833336
986 654104778536
987 656905043504
988 659715528298
989 662537106650
990 665366748950
991 668211991726
992 671063516164
993 673925652120
994 676795404516
995 679674471152
996 682561441390
997 685458848082
998 688362605890
999 691273214806
1000 694194100732