0 1
1 0
2 1
3 1
4 3
5 3
6 4
7 4
8 10
9 12
10 14
11 16
12 19
13 21
14 24
15 27
16 64
17 72
18 84
19 94
20 108
21 120
22 136
23 150
24 169
25 185
26 206
27 225
28 249
29 270
30 297
31 321
32 831
33 918
34 1014
35 1115
36 1226
37 1342
38 1469
39 1602
40 1747
41 1898
42 2062
43 2233
44 2418
45 2611
46 2818
47 3034
48 3266
49 3507
50 3765
51 4033
52 4319
53 4616
54 4932
55 5260
56 5608
57 5969
58 6351
59 6747
60 7166
61 7599
62 8056
63 8529
64 26207
65 28009
66 29941
67 31943
68 34085
69 36308
70 38677
71 41134
72 43752
73 46461
74 49342
75 52327
76 55491
77 58767
78 62239
79 65827
80 69624
81 73551
82 77695
83 81979
84 86499
85 91164
86 96079
87 101155
88 106491
89 111999
90 117788
91 123755
92 130019
93 136479
94 143247
95 150224
96 157532
97 165056
98 172929
99 181038
100 189509
101 198230
102 207338
103 216705
104 226479
105 236534
106 247010
107 257783
108 269005
109 280534
110 292534
111 304865
112 317683
113 330850
114 344534
115 358579
116 373165
117 388138
118 403670
119 419609
120 436140
121 453091
122 470660
123 488678
124 507334
125 526461
126 546261
127 566547
128 2239706
129 2336282
130 2436354
131 2539915
132 2647176
133 2758123
134 2872974
135 2991725
136 3114593
137 3241575
138 3372904
139 3508570
140 3648814
141 3793635
142 3943274
143 4097732
144 4257266
145 4421870
146 4591809
147 4767088
148 4947971
149 5134465
150 5326852
151 5525131
152 5729593
153 5940248
154 6157387
155 6381022
156 6611462
157 6848712
158 7093090
159 7344613
160 7603599
161 7870067
162 8144354
163 8426472
164 8716768
165 9015266
166 9322313
167 9637936
168 9962502
169 10296030
170 10638898
171 10991138
172 11353128
173 11724903
174 12106862
175 12499033
176 12901825
177 13315280
178 13739808
179 14175454
180 14622650
181 15081433
182 15552247
183 16035143
184 16530566
185 17038571
186 17559625
187 18093776
188 18641503
189 19202869
190 19778354
191 20368025
192 20972386
193 21591496
194 22225872
195 22875589
196 23541165
197 24222679
198 24920674
199 25635222
200 26366879
201 27115733
202 27882342
203 28666799
204 29469687
205 30291092
206 31131611
207 31991347
208 32870899
209 33770375
210 34690401
211 35631077
212 36593044
213 37576420
214 38581848
215 39609452
216 40659902
217 41733315
218 42830376
219 43951221
220 45096538
221 46266468
222 47461728
223 48682452
224 49929373
225 51202644
226 52503001
227 53830604
228 55186218
229 56569996
230 57982720
231 59424563
232 60896310
233 62398141
234 63930872
235 65494676
236 67090386
237 68718196
238 70378943
239 72072828
240 73800720
241 75562813
242 77359994
243 79192479
244 81061159
245 82966258
246 84908699
247 86888700
248 88907203
249 90964448
250 93061382
251 95198253
252 97376042
253 99594990
254 101856098
255 104159631
256 567852809
257 582538824
258 597551430
259 612892037
260 628571262
261 644590591
262 660960912
263 677683798
264 694770420
265 712222416
266 730051254
267 748258664
268 766856392
269 785846254
270 805240304
271 825040439
272 845259018
273 865898029
274 886970134
275 908477424
276 930432877
277 952838664
278 975708094
279 999043446
280 1022858341
281 1047155159
282 1071947864
283 1097238934
284 1123042672
285 1149361664
286 1176210551
287 1203592039
288 1231521121
289 1260000599
290 1289045834
291 1318659754
292 1348858067
293 1379643821
294 1411033104
295 1443029079
296 1475648211
297 1508893789
298 1542782654
299 1577318234
300 1612517760
301 1648384775
302 1684936916
303 1722177872
304 1760125666
305 1798784126
306 1838171695
307 1878292336
308 1919164909
309 1960793523
310 2003197454
311 2046380971
312 2090363781
313 2135150288
314 2180760647
315 2227199430
316 2274487218
317 2322628744
318 2371645052
319 2421541031
320 2472338185
321 2524041571
322 2576673152
323 2630238168
324 2684759056
325 2740241214
326 2796707571
327 2854163716
328 2912633049
329 2972121343
330 3032652506
331 3094232491
332 3156885711
333 3220618312
334 3285455211
335 3351402762
336 3418486403
337 3486712669
338 3556107538
339 3626677762
340 3698449836
341 3771430722
342 3845647471
343 3921107251
344 3997837666
345 4075846103
346 4155160719
347 4235789136
348 4317760081
349 4401081384
350 4485782362
351 4571871089
352 4659377449
353 4748309754
354 4838698495
355 4930552218
356 5023902018
357 5118756689
358 5215147930
359 5313084799
360 5412599618
361 5513701681
362 5616423953
363 5720776003
364 5826791415
365 5934480026
366 6043876081
367 6154989681
368 6267855730
369 6382484607
370 6498911875
371 6617148209
372 6737229849
373 6859167738
374 6982998815
375 7108734330
376 7236411897
377 7366043066
378 7497666170
379 7631293055
380 7766962770
381 7904687473
382 8044506929
383 8186433626
384 8330508065
385 8476743035
386 8625179795
387 8775831476
388 8928740071
389 9083919046
390 9241411173
391 9401230249
392 9563419823
393 9727994039
394 9894997223
395 10064443886
396 10236379151
397 10410817866
398 10587805975
399 10767358705
400 10949522796
401 11134313847
402 11321779441
403 11511935546
404 11704830585
405 11900480912
406 12098935791
407 12300211981
408 12504359609
409 12711395809
410 12921371595
411 13134304520
412 13350246459
413 13569215378
414 13791264061
415 14016410883
416 14244709536
417 14476178821
418 14710873339
419 14948812338
420 15190051350
421 15434610039
422 15682544893
423 15933876038
424 16188660892
425 16446920036
426 16708711868
427 16974057421
428 17243016071
429 17515609321
430 17791897527
431 18071902683
432 18355686148
433 18643270376
434 18934717755
435 19230051246
436 19529334239
437 19832590196
438 20139883561
439 20451238293
440 20766719889
441 21086352824
442 21410203649
443 21738297378
444 22070701640
445 22407441956
446 22748587060
447 23094163028
448 23444239673
449 23798843619
450 24158045811
451 24521873419
452 24890398518
453 25263648844
454 25641697604
455 26024573123
456 26412349765
457 26805056411
458 27202768611
459 27605515852
460 28013374842
461 28426375668
462 28844596251
463 29268067275
464 29696867873
465 30131029347
466 30570632044
467 31015707908
468 31466338526
469 31922556451
470 32384444539
471 32852036003
472 33325414941
473 33804615220
474 34289722236
475 34780770508
476 35277846729
477 35780986091
478 36290276587
479 36805754107
480 37327507971
481 37855574733
482 38390045070
483 38930956254
484 39478400290
485 40032415162
486 40593094262
487 41160476283
488 41734656004
489 42315672849
490 42903622987
491 43498546599
492 44100541271
493 44709647908
494 45325965544
495 45949535862
496 46580459316
497 47218778361
498 47864594931
499 48517952251
500 49178953735
501 49847643401
502 50524126146
503 51208446808
504 51900711796
505 52600966733
506 53309319572
507 54025816778
508 54750567819
509 55483619996
510 56225084354
511 56975009028
512 454241403975
513 461088843747
514 468026433272
515 475055171285
516 482176099226
517 489390234128
518 496698637145
519 504102344803
520 511602437364
521 519199971116
522 526896046625
523 534691739344
524 542588170436
525 550586435711
526 558687676312
527 566893008718
528 575203595279
529 583620572501
530 592145124244
531 600778408297
532 609521629403
533 618375966922
534 627342647737
535 636422872161
536 645617889530
537 654928922362
538 664357241809
539 673904092927
540 683570769971
541 693358539872
542 703268720312
543 713302601415
544 723461523642
545 733746800618
546 744159796902
547 754701848982
548 765374345849
549 776178648168
550 787116168704
551 798188292653
552 809396457905
553 820742073503
554 832226602806
555 843851480086
556 855618193503
557 867528202887
558 879583022582
559 891784137317
560 904133087976
561 916631385565
562 929280596829
563 942082259428
564 955037967383
565 968149284303
566 981417831852
567 994845201035
568 1008433040470
569 1022182968909
570 1036096663373
571 1050175769682
572 1064421993638
573 1078837009573
574 1093422551371
575 1108180322275
576 1123112085733
577 1138219573173
578 1153504577997
579 1168968861333
580 1184614245827
581 1200442522681
582 1216455545301
583 1232655134264
584 1249043174138
585 1265621516386
586 1282392076018
587 1299356735807
588 1316517442756
589 1333876110200
590 1351434717549
591 1369195210284
592 1387159599492
593 1405329863198
594 1423708045751
595 1442296157001
596 1461096274985
597 1480110442959
598 1499340771908
599 1518789338942
600 1538458289615
601 1558349734123
602 1578465853028
603 1598808791267
604 1619380763659
605 1640183950305
606 1661220601938
607 1682492933083
608 1704003230839
609 1725753745807
610 1747746800691
611 1769984682643
612 1792469751665
613 1815204330671
614 1838190817426
615 1861431572334
616 1884929030152
617 1908685589222
618 1932703723023
619 1956985867076
620 1981534534060
621 2006352198400
622 2031441411194
623 2056804686273
624 2082444614921
625 2108363749565
626 2134564722167
627 2161050125553
628 2187822631572
629 2214884873924
630 2242239566150
631 2269889382044
632 2297837077345
633 2326085367742
634 2354637050370
635 2383494883343
636 2412661707035
637 2442140321155
638 2471933609836
639 2502044416261
640 2532475667511
641 2563230250746
642 2594311137877
643 2625721259242
644 2657463632116
645 2689541231892
646 2721957120388
647 2754714318611
648 2787815934843
649 2821265034854
650 2855064773939
651 2889218264590
652 2923728708283
653 2958599264764
654 2993833183651
655 3029433671125
656 3065404025510
657 3101747501378
658 3138467444918
659 3175567159682
660 3213050041725
661 3250919442708
662 3289178809131
663 3327831542803
664 3366881139818
665 3406331052695
666 3446184829163
667 3486445971613
668 3527118080004
669 3568204708636
670 3609709508837
671 3651636087436
672 3693988149213
673 3736769352635
674 3779983456544
675 3823634173167
676 3867725314537
677 3912260647234
678 3957244038607
679 4002679308731
680 4048570380897
681 4094921130795
682 4141735536778
683 4189017530804
684 4236771148454
685 4285000377043
686 4333709310023
687 4382901992272
688 4432582574223
689 4482755158942
690 4533423956052
691 4584593125931
692 4636266938051
693 4688449612307
694 4741145477120
695 4794358812588
696 4848094008334
697 4902355403728
698 4957147450271
699 5012474548898
700 5068341212079
701 5124751902972
702 5181711197312
703 5239223619585
704 5297293809484
705 5355926355115
706 5415125959210
707 5474897274216
708 5535245068244
709 5596174057132
710 5657689075081
711 5719794903701
712 5782496442355
713 5845798539118
714 5909706160900
715 5974224221327
716 6039357755584
717 6105111745229
718 6171491292785
719 6238501448498
720 6306147384659
721 6374434219233
722 6443367195025
723 6512951500192
724 6583192447106
725 6654095294844
726 6725665427821
727 6797908175102
728 6870828993910
729 6944433285769
730 7018726579754
731 7093714350642
732 7169402201882
733 7245795680516
734 7322900465150
735 7400722177656
736 7479266570832
737 7558539342145
738 7638546321154
739 7719293279971
740 7800786125718
741 7883030707717
742 7966033009679
743 8049798958967
744 8134334618497
745 8219645992667
746 8305739224419
747 8392620397846
748 8480295734933
749 8568771400271
750 8658053697552
751 8748148870897
752 8839063306546
753 8930803330810
754 9023375411485
755 9116785957943
756 9211041522248
757 9306148595808
758 9402113815816
759 9498943758473
760 9596645145100
761 9695224637533
762 9794689043982
763 9895045110934
764 9996299734368
765 10098459748179
766 10201532135106
767 10305523817363
768 10410441867260
769 10516293294287
770 10623085261226
771 10730824867699
772 10839519365942
773 10949175946592
774 11059801954199
775 11171404669413
776 11283991530020
777 11397569909540
778 11512147337968
779 11627731282647
780 11744329368692
781 11861949156209
782 11980598366376
783 12100284655019
784 12221015838344
785 12342799668821
786 12465644060646
787 12589556861915
788 12714546085778
789 12840619678915
790 12967785752387
791 13096052352454
792 13225427691101
793 13355919913091
794 13487537332319
795 13620288195112
796 13754180916223
797 13889223844510
798 14025425498650
799 14162794328997
800 14301338959160
801 14441067944051
802 14581990011151
803 14724113820971
804 14867448207982
805 15012001937200
806 15157783951116
807 15304803122417
808 15453068500547
809 15602589066875
810 15753373980969
811 15905432331830
812 16058773390203
813 16213406355889
814 16369340609734
815 16526585463425
816 16685150411134
817 16845044875324
818 17006278464569
819 17168860715382
820 17332801349655
821 17498110019008
822 17664796561931
823 17832870744085
824 18002342521657
825 18173221777625
826 18345518584782
827 18519242944556
828 18694405049680
829 18871015018906
830 19049083166030
831 19228619730512
832 19409635146112
833 19592139774102
834 19776144171595
835 19961658820595
836 20148694402715
837 20337261524077
838 20527370989688
839 20719033530969
840 20912260079767
841 21107061491660
842 21303448826506
843 21501433067537
844 21701025401508
845 21902236940457
846 22105079001538
847 22309562824500
848 22515699858092
849 22723501473273
850 22932979249266
851 23144144689471
852 23357009507144
853 23571585336970
854 23787884027459
855 24005917348191
856 24225697281802
857 24447235733969
858 24670544825071
859 24895636595773
860 25122523305443
861 25351217133348
862 25581730476710
863 25814075654680
864 26048265206009
865 26284311588561
866 26522227483888
867 26762025492295
868 27003718436993
869 27247319061980
870 27492840335860
871 27740295145202
872 27989696605301
873 28241057749028
874 28494391837220
875 28749712050385
876 29007031798695
877 29266364409110
878 29527723442462
879 29791122376009
880 30056574920088
881 30324094703560
882 30593695590120
883 30865391359097
884 31139196028895
885 31415123533162
886 31693188043849
887 31973403650311
888 32255784681960
889 32540345382660
890 32827100240662
891 33116063658307
892 33407250281517
893 33700674672469
894 33996351638731
895 34294295901168
896 34594522430400
897 34897046109952
898 35201882072322
899 35509045365139
900 35818551286815
901 36130415047872
902 36444652114070
903 36761277862916
904 37080307926337
905 37401757850239
906 37725643436815
907 38051980399211
908 38380784711348
909 38712072257708
910 39045859182754
911 39382161543804
912 39720995660025
913 40062377760348
914 40406324340134
915 40752851804145
916 41101976822744
917 41453715977995
918 41808086119488
919 42165104005418
920 42524786666122
921 42887151040149
922 43252214337385
923 43619993678292
924 43990506456594
925 44363769973431
926 44739801807914
927 45118619446207
928 45500240651605
929 45884683096825
930 46271964733700
931 46662103420319
932 47055117298631
933 47451024416449
934 47849843104630
935 48251591602329
936 48656288433730
937 49063952028084
938 49474601104511
939 49888254286835
940 50304930487898
941 50724648527686
942 51147427517248
943 51573286471541
944 52002244701460
945 52434321421416
946 52869536140931
947 53307908275550
948 53749457537974
949 54194203543625
950 54642166210053
951 55093365357167
952 55547821106143
953 56005553483027
954 56466582817239
955 56930929339762
956 57398613589961
957 57869656008373
958 58344077343080
959 58821898245915
960 59303139678363
961 59787822502287
962 60275967894308
963 60767596931065
964 61262731003082
965 61761391403487
966 62263599741462
967 62769377525414
968 63278746584948
969 63791728648503
970 64308345764870
971 64828619884327
972 65352573279674
973 65880228121753
974 66411606909170
975 66946732038215
976 67485626232059
977 68028312114217
978 68574812637318
979 69125150650885
980 69679349338835
981 70237431781590
982 70799421393110
983 71365341486589
984 71935215710993
985 72509067611004
986 73086921072457
987 73668799876547
988 74254728144729
989 74844729896554
990 75438829494131
991 76037051194142
992 76639419601247
993 77245959214292
994 77856694879235
995 78471651339026
996 79090853686026
997 79714326905998
998 80342096339637
999 80974187220686
1000 81610625136918