0 1
1 0
2 0
3 1
4 1
5 0
6 1
7 1
8 2
9 2
10 1
11 2
12 3
13 2
14 2
15 4
16 5
17 4
18 5
19 6
20 7
21 7
22 7
23 9
24 12
25 11
26 11
27 15
28 16
29 16
30 18
31 21
32 24
33 25
34 26
35 31
36 36
37 35
38 38
39 45
40 50
41 51
42 55
43 63
44 69
45 73
46 77
47 87
48 98
49 101
50 107
51 122
52 132
53 138
54 149
55 164
56 180
57 190
58 201
59 222
60 243
61 254
62 271
63 300
64 324
65 340
66 364
67 397
68 428
69 453
70 481
71 523
72 566
73 595
74 632
75 688
76 737
77 777
78 829
79 894
80 959
81 1014
82 1074
83 1158
84 1241
85 1307
86 1387
87 1493
88 1594
89 1681
90 1785
91 1911
92 2037
93 2152
94 2278
95 2436
96 2598
97 2737
98 2897
99 3097
100 3289
101 3467
102 3672
103 3910
104 4152
105 4380
106 4626
107 4922
108 5223
109 5500
110 5809
111 6175
112 6539
113 6886
114 7272
115 7712
116 8159
117 8593
118 9061
119 9599
120 10154
121 10680
122 11255
123 11917
124 12581
125 13231
126 13943
127 14734
128 15548
129 16350
130 17206
131 18169
132 19160
133 20128
134 21175
135 22345
136 23535
137 24717
138 25992
139 27392
140 28831
141 30273
142 31805
143 33494
144 35239
145 36969
146 38822
147 40859
148 42941
149 45035
150 47276
151 49703
152 52209
153 54740
154 57415
155 60326
156 63334
157 66358
158 69574
159 73059
160 76642
161 80272
162 84127
163 88268
164 92546
165 96898
166 101486
167 106419
168 111530
169 116706
170 122177
171 128054
172 134106
173 140279
174 146802
175 153753
176 160949
177 168299
178 176022
179 184265
180 192801
181 201503
182 210667
183 220429
184 230510
185 240827
186 251682
187 263189
188 275102
189 287319
190 300122
191 313699
192 327769
193 342168
194 357277
195 373283
196 389824
197 406807
198 424623
199 443414
200 462882
201 482889
202 503808
203 525889
204 548765
205 572250
206 596831
207 622741
208 649546
209 677118
210 705960
211 736278
212 767679
213 800012
214 833761
215 869233
216 905992
217 943797
218 983277
219 1024743
220 1067646
221 1111846
222 1157986
223 1206333
224 1256413
225 1308029
226 1361814
227 1418177
228 1476559
229 1536696
230 1599383
231 1665017
232 1732943
233 1802981
234 1875956
235 1952236
236 2031223
237 2112704
238 2197494
239 2286106
240 2377877
241 2472485
242 2570946
243 2673789
244 2780202
245 2889998
246 3004229
247 3123371
248 3246718
249 3374009
250 3506297
251 3644261
252 3787079
253 3934408
254 4087534
255 4247133
256 4412255
257 4582672
258 4759737
259 4944094
260 5134874
261 5331812
262 5536262
263 5749086
264 5969324
265 6196580
266 6432495
267 6677965
268 6931845
269 7193920
270 7465905
271 7748648
272 8041142
273 8343092
274 8656242
275 8981723
276 9318388
277 9665840
278 10026163
279 10400508
280 10787565
281 11187110
282 11601334
283 12031387
284 12476067
285 12935117
286 13410774
287 13904490
288 14414966
289 14941786
290 15487605
291 16053954
292 16639299
293 17243490
294 17869318
295 18518290
296 19189067
297 19881417
298 20598221
299 21341392
300 22109430
301 22901999
302 23722469
303 24572834
304 25451396
305 26358077
306 27296452
307 28268550
308 29272853
309 30309269
310 31381495
311 32492015
312 33639203
313 34822817
314 36047158
315 37314873
316 38624073
317 39974894
318 41371903
319 42817782
320 44310928
321 45851432
322 47444057
323 49092090
324 50793762
325 52549087
326 54363563
327 56240651
328 58178394
329 60177202
330 62242934
331 64379201
332 66584324
333 68858781
334 71208698
335 73638378
336 76146071
337 78732140
338 81403629
339 84165150
340 87014702
341 89953228
342 92988244
343 96124548
344 99360585
345 102697350
346 106142768
347 109702543
348 113375019
349 117161211
350 121070145
351 125107920
352 129272732
353 133566253
354 137998159
355 142574902
356 147295176
357 152160872
358 157182233
359 162366775
360 167713246
361 173223569
362 178909366
363 184778782
364 190830395
365 197067057
366 203501248
367 210141575
368 216987376
369 224041776
370 231318056
371 238826234
372 246565720
373 254539907
374 262763778
375 271248140
376 279992452
377 289001193
378 298290518
379 307871996
380 317745976
381 327917514
382 338403842
383 349218247
384 360361422
385 371838797
386 383669768
387 395868785
388 408436675
389 421380393
390 434720870
391 448473586
392 462640671
393 477229849
394 492263551
395 507759514
396 523720374
397 540154625
398 557087413
399 574537989
400 592509500
401 611012318
402 630073659
403 649714330
404 669939095
405 690759608
406 712205110
407 734299207
408 757047668
409 780463230
410 804578585
411 829419519
412 854992587
413 881313134
414 908416585
415 936330803
416 965064678
417 994635268
418 1025080790
419 1056432791
420 1088701573
421 1121906007
422 1156088671
423 1191283992
424 1227503757
425 1264770125
426 1303129351
427 1342618847
428 1383253402
429 1425057792
430 1468081999
431 1512368107
432 1557933199
433 1604804569
434 1653037813
435 1702679013
436 1753747423
437 1806274835
438 1860321712
439 1915938140
440 1973147585
441 2031985383
442 2092517037
443 2154798811
444 2218857361
445 2284731824
446 2352494887
447 2422208102
448 2493901590
449 2567620275
450 2643443337
451 2721437938
452 2801639690
453 2884098666
454 2968900781
455 3056121086
456 3145800007
457 3237992810
458 3332794709
459 3430288010
460 3530517994
461 3633547812
462 3739481239
463 3848408103
464 3960381275
465 4075470835
466 4193789619
467 4315437854
468 4440475041
469 4568978732
470 4701073734
471 4836869895
472 4976433889
473 5119853534
474 5267265025
475 5418788517
476 5574500698
477 5734499114
478 5898932010
479 6067932985
480 6241588209
481 6420005386
482 6603348300
483 6791763582
484 6985347301
485 7184220984
486 7388563462
487 7598535087
488 7814245618
489 8035829638
490 8263482035
491 8497380907
492 8737648894
493 8984434780
494 9237953563
495 9498400575
496 9765912514
497 10040656250
498 10322866722
499 10612757831
500 10910484353
501 11216231132
502 11530254369
503 11852791019
504 12184013809
505 12524126674
506 12873412007
507 13232129868
508 13600472123
509 13978666917
510 14367022884
511 14765824758
512 15175288810
513 15595667200
514 16027296769
515 16470492570
516 16925495089
517 17392582604
518 17872125969
519 18364470739
520 18869883838
521 19388675319
522 19921250645
523 20467988437
524 21029187869
525 21605191514
526 22196442066
527 22803357614
528 23426270429
529 24065557975
530 24721707230
531 25395176904
532 26086334833
533 26795600761
534 27523507134
535 28270556342
536 29037159427
537 29823779314
538 30630997602
539 31459368501
540 32309347286
541 33181443967
542 34076297687
543 34994516130
544 35936602866
545 36903123331
546 37894776453
547 38912227941
548 39956038339
549 41026830936
550 42125369232
551 43252386473
552 44408502783
553 45594403952
554 46810928395
555 48058880050
556 49338943494
557 50651877797
558 51998599694
559 53379989489
560 54796807448
561 56249889102
562 57740236014
563 59268816925
564 60836471185
565 62444117705
566 64092855416
567 65783745761
568 67517714499
569 69295776466
570 71119133132
571 72988946749
572 74906242529
573 76872136838
574 78887942200
575 80954935966
576 83074248779
577 85247106978
578 87474949709
579 89759176203
580 92101031497
581 94501868131
582 96963259121
583 99486735818
584 102073674535
585 104725561264
586 107444114319
587 110231015282
588 113087779534
589 116016038553
590 119017674944
591 122094529611
592 125248269706
593 128480691486
594 131793852236
595 135189766156
596 138670272330
597 142237342843
598 145893224521
599 149640126762
600 153480072393
601 157415224402
602 161448042788
603 165580945389
604 169816154664
605 174156049266
606 178603316532
607 183160600451
608 187830349094
609 192615171150
610 197518000878
611 202541736246
612 207689066259
613 212962850357
614 218366298934
615 223902581324
616 229574649344
617 235385643085
618 241339068498
619 247438390098
620 253686853910
621 260087901283
622 266645359020
623 273363020883
624 280244448997
625 287293412004
626 294514094211
627 301910642697
628 309486963300
629 317247190313
630 325195891349
631 333337597178
632 341676597615
633 350217419293
634 358965046221
635 367924436053
636 377100290971
637 386497564860
638 396121703729
639 405978123565
640 416071975904
641 426408688921
642 436994205120
643 447834438976
644 458935040786
645 470301949623
646 481941647178
647 493860599717
648 506064995293
649 518561328082
650 531356676214
651 544458100215
652 557872372690
653 571606603073
654 585668511263
655 600065803148
656 614805899153
657 629896571146
658 645346236173
659 661163313160
660 677355920569
661 693932551127
662 710902390558
663 728274625864
664 746058135370
665 764262206973
666 782896854826
667 801972100707
668 821497661138
669 841483682417
670 861941078133
671 882880789088
672 904313437149
673 926250101133
674 948702684180
675 971683118848
676 995203010842
677 1019274466200
678 1043910455314
679 1069123987457
680 1094927752056
681 1121334963641
682 1148359751295
683 1176016307864
684 1204318492759
685 1233280725631
686 1262918407323
687 1293247007883
688 1324281659112
689 1356038103657
690 1388533115195
691 1421783551011
692 1455805939636
693 1490617453742
694 1526236356814
695 1562681026801
696 1599969502543
697 1638120509223
698 1677153942665
699 1717089823757
700 1757947831454
701 1799748393440
702 1842513168192
703 1886263959460
704 1931022244546
705 1976810290492
706 2023651668430
707 2071570133870
708 2120589107788
709 2170732854953
710 2222027038115
711 2274497521300
712 2328169836855
713 2383070434701
714 2439227237392
715 2496668397243
716 2555421755831
717 2615516126133
718 2676981881689
719 2739849674702
720 2804149844787
721 2869913768684
722 2937174496442
723 3005965382775
724 3076319477846
725 3148270959841
726 3221855770958
727 3297110196463
728 3374070248153
729 3452773132470
730 3533257927541
731 3615564116831
732 3699730914296
733 3785798812240
734 3873810308247
735 3963808342312
736 4055835603310
737 4149936166910
738 4246156226549
739 4344542470196
740 4445141376024
741 4548000895360
742 4653171227039
743 4760703142695
744 4870647219576
745 4983055610416
746 5097982876611
747 5215484204756
748 5335614616185
749 5458430841537
750 5583992157084
751 5712358533376
752 5843589833609
753 5977747737573
754 6114896629753
755 6255101688207
756 6398428011430
757 6544942643859
758 6694715527044
759 6847817467442
760 7004319238789
761 7164293722033
762 7327816864672
763 7494965570837
764 7665816788064
765 7840449708524
766 8018946783695
767 8201391546569
768 8387867621494
769 8578461036402
770 8773261311300
771 8972359144621
772 9175845392743
773 9383813514937
774 9596360669546
775 9813585312858
776 10035586162646
777 10262464710294
778 10494326382911
779 10731278063744
780 10973426968356
781 11220883286197
782 11473761421837
783 11732177364632
784 11996247532586
785 12266091559322
786 12541833549622
787 12823599348999
788 13111515366527
789 13405711443859
790 13706322181561
791 14013484120108
792 14327334468395
793 14648014114881
794 14975669046095
795 15310447358611
796 15652497948590
797 16001973690524
798 16359032870614
799 16723836086236
800 17096544913442
801 17477325176583
802 17866348465066
803 18263788931309
804 18669821851419
805 19084627059670
806 19508390564869
807 19941301160518
808 20383548944250
809 20835328936111
810 21296842718180
811 21768294916886
812 22249891693904
813 22741844474460
814 23244371676825
815 23757695080191
816 24282038200580
817 24817630200258
818 25364707733148
819 25923511102446
820 26494282587231
821 27077270563503
822 27672731374218
823 28280925343787
824 28902115074523
825 29536569689783
826 30184566809782
827 30846388435153
828 31522319113971
829 32212650394083
830 32917682924551
831 33637722106339
832 34373076206590
833 35124061043963
834 35891002125279
835 36674230133942
836 37474079006765
837 38290890765135
838 39125017766701
839 39976818046417
840 40846653253982
841 41734893715798
842 42641920831906
843 43568122157294
844 44513889276821
845 45479623134539
846 46465736469243
847 47472648714056
848 48500783832078
849 49550575807903
850 50622471217833
851 51716923962010
852 52834392943402
853 53975347825410
854 55140271760006
855 56329655832390
856 57543996673581
857 58783802512529
858 60049595956858
859 61341908232199
860 62661276746720
861 64008251335967
862 65383397190277
863 66787288906640
864 68220507884513
865 69683648864678
866 71177323039351
867 72702151783501
868 74258763973384
869 75847802862299
870 77469929249048
871 79125814980384
872 80816140218621
873 82541600532829
874 84302910238191
875 86100795686220
876 87935992344019
877 89809252222989
878 91721347418118
879 93673063043868
880 95665194231274
881 97698553929049
882 99773976518854
883 101892310493926
884 104054415395008
885 106261169865428
886 108513475453973
887 110812249056076
888 113158419647788
889 115552936714374
890 117996774283753
891 120490922974157
892 123036386632876
893 125634191190537
894 128285388779494
895 130991049495332
896 133752257971500
897 136570122517610
898 139445779456311
899 142380384616983
900 145375109685793
901 148431151772349
902 151549737999452
903 154732116562993
904 157979552981062
905 161293340131780
906 164674802951531
907 168125289173904
908 171646165503594
909 175238827987107
910 178904706951702
911 182645257446441
912 186461955175242
913 190356307343263
914 194329857886812
915 198384177433611
916 202520859120879
917 206741529978713
918 211047856282921
919 215441533159067
920 219924280322194
921 224497853833772
922 229164051733685
923 233924703310406
924 238781664574052
925 243736830557653
926 248792141270183
927 253949570437471
928 259211120854508
929 264578837282261
930 270054812554220
931 275641175920028
932 281340088306906
933 287153755652828
934 293084435322035
935 299134424078264
936 305306053062101
937 311601701729067
938 318023804634827
939 324574838823380
940 331257318668265
941 338073810489320
942 345026939512124
943 352119376817501
944 359353834088721
945 366733078718831
946 374259941128501
947 381937301301786
948 389768083221363
949 397755270666841
950 405901914942147
951 414211120769578
952 422686040582825
953 431329891080034
954 440145961165611
955 449137597356950
956 458308197971225
957 467661230248677
958 477200238693649
959 486928830024122
960 496850667027690
961 506969486455187
962 517289107832414
963 527813417703279
964 538546363327584
965 549491971433758
966 560654357275974
967 572037708340663
968 583646277936966
969 595484404591587
970 607556521568303
971 619867140067319
972 632420842454447
973 645222302535703
974 658276295600428
975 671587680848051
976 685161394455062
977 699002470806318
978 713116052837673
979 727507373869361
980 742181750554229
981 757144604854220
982 772401474899751
983 787957996266206
984 803819894541687
985 819993008286206
986 836483300493737
987 853296839020882
988 870439788978116
989 887918436777242
990 905739201937466
991 923908616864571
992 942433319124849
993 961320076334101
994 980575798561882
995 1000207517496312
996 1020222378307357
997 1040627665656654
998 1061430816776046
999 1082639399708556
1000 1104261104994428