0 1
1 0
2 1
3 1
4 2
5 2
6 5
7 4
8 9
9 10
10 16
11 19
12 31
13 34
14 53
15 64
16 89
17 109
18 152
19 179
20 245
21 296
22 384
23 467
24 601
25 716
26 911
27 1090
28 1351
29 1614
30 1986
31 2342
32 2856
33 3364
34 4037
35 4742
36 5653
37 6578
38 7791
39 9036
40 10592
41 12243
42 14268
43 16380
44 18990
45 21724
46 24999
47 28501
48 32643
49 37017
50 42218
51 47713
52 54112
53 60968
54 68869
55 77264
56 86971
57 97271
58 109014
59 121588
60 135812
61 150946
62 168101
63 186326
64 206769
65 228627
66 252990
67 278912
68 307849
69 338576
70 372616
71 408923
72 448934
73 491451
74 538348
75 588089
76 642630
77 700660
78 764021
79 831228
80 904658
81 982400
82 1066943
83 1156661
84 1253876
85 1356786
86 1468340
87 1586220
88 1713529
89 1848282
90 1993376
91 2146632
92 2311684
93 2485744
94 2672628
95 2869960
96 3081281
97 3304016
98 3542573
99 3793640
100 4061867
101 4344419
102 4645602
103 4962390
104 5300075
105 5654779
106 6032079
107 6428660
108 6849684
109 7291632
110 7760812
111 8252700
112 8773951
113 9320706
114 9899100
115 10505092
116 11146109
117 11816947
118 12525460
119 13267199
120 14049409
121 14867457
122 15730052
123 16631238
124 17580212
125 18571901
126 19614766
127 20703567
128 21848425
129 23042571
130 24296718
131 25605091
132 26977537
133 28408150
134 29908618
135 31471318
136 33108611
137 34814004
138 36598862
139 38456572
140 40400571
141 42422290
142 44535947
143 46734263
144 49030282
145 51416659
146 53908725
147 56496938
148 59197538
149 62002413
150 64926475
151 67961574
152 71125153
153 74406618
154 77824428
155 81369610
156 85059090
157 88883908
158 92863795
159 96987046
160 101274567
161 105716442
162 110331836
163 115110922
164 120075925
165 125213992
166 130548656
167 136069052
168 141796763
169 147721058
170 153866896
171 160220180
172 166807339
173 173616492
174 180671852
175 187961773
176 195514136
177 203313584
178 211389660
179 219729427
180 228359972
181 237268660
182 246486577
183 255997027
184 265832921
185 275980247
186 286469160
187 297286049
188 308465431
189 319989218
190 331893978
191 344164546
192 356834430
193 369888992
194 383366443
195 397247278
196 411571955
197 426324164
198 441540998
199 457206767
200 473363678
201 489990713
202 507132557
203 524771696
204 542949075
205 561647958
206 580914789
207 600727038
208 621133891
209 642116601
210 663720273
211 685927058
212 708787986
213 732278942
214 756453931
215 781292972
216 806845574
217 833092810
218 860090580
219 887813144
220 916319682
221 945588906
222 975675083
223 1006558170
224 1038299263
225 1070870986
226 1104337986
227 1138677700
228 1173949441
229 1210132042
230 1247292164
231 1285400709
232 1324528199
233 1364650749
234 1405833048
235 1448052834
236 1491382632
237 1535791643
238 1581356604
239 1628052295
240 1675949157
241 1725023778
242 1775354970
243 1826910173
244 1879772723
245 1933916088
246 1989416762
247 2046250248
248 2104501990
249 2164137644
250 2225247576
251 2287803882
252 2351889536
253 2417478933
254 2484664546
255 2553410259
256 2623813823
257 2695846020
258 2769596656
259 2845039036
260 2922273102
261 3001260892
262 3082108029
263 3164783954
264 3249385702
265 3335885544
266 3424391255
267 3514863076
268 3607414911
269 3702014869
270 3798767664
271 3897644497
272 3998761477
273 4102077006
274 4207713727
275 4315638469
276 4425963989
277 4538660516
278 4653852908
279 4771497728
280 4891726868
281 5014505834
282 5139955933
283 5268046424
284 5398911383
285 5532505574
286 5668970563
287 5808270627
288 5950536041
289 6095735140
290 6244011739
291 6395318748
292 6549807978
293 6707442471
294 6868361944
295 7032533898
296 7200112320
297 7371048347
298 7545504519
299 7723442683
300 7905012525
301 8090180701
302 8279111954
303 8471755632
304 8668285541
305 8868662418
306 9073046352
307 9281403291
308 9493909225
309 9710511739
310 9931396502
311 10156523122
312 10386062682
313 10619980453
314 10858464221
315 11101459884
316 11349165471
317 11601539595
318 11858764826
319 12120805840
320 12387862823
321 12659879954
322 12937068286
323 13219385460
324 13507026086
325 13799954373
326 14098383417
327 14402255799
328 14711796159
329 15026961240
330 15347958304
331 15674751114
332 16007566349
333 16346345004
334 16691325929
335 17042465095
336 17399982925
337 17763842916
338 18134285902
339 18511251354
340 18894993019
341 19285466106
342 19682904880
343 20087272640
344 20498825008
345 20917500046
346 21343566977
347 21776980427
348 22217989076
349 22666556146
350 23122952744
351 23587115520
352 24059329932
353 24539550081
354 25028039701
355 25524762112
356 26030004494
357 26543702252
358 27066157728
359 27597324614
360 28137482399
361 28686594556
362 29244965109
363 29812528265
364 30389603965
365 30976145660
366 31572449186
367 32178478401
368 32794554830
369 33420611583
370 34056986983
371 34703634289
372 35360866458
373 36028647842
374 36707318191
375 37396809680
376 38097479679
377 38809281483
378 39532545831
379 40267237735
380 41013715964
381 41771911789
382 42542202489
383 43324541494
384 44119278054
385 44926378068
386 45746219998
387 46578734430
388 47424319291
389 48282928308
390 49154930040
391 50040291370
392 50939411325
393 51852219892
394 52779136460
395 53720115273
396 54675544876
397 55645393423
398 56630081256
399 57629537912
400 58644205125
401 59674037745
402 60719445180
403 61780397012
404 62857335718
405 63950190596
406 65059426484
407 66184999123
408 67327339536
409 68486418950
410 69662702873
411 70856120438
412 72067160555
413 73295780002
414 74542432242
415 75807090432
416 77090243877
417 78391821819
418 79712338078
419 81051750682
420 82410536435
421 83788670566
422 85186667158
423 86604455695
424 88042575822
425 89500987094
426 90980190425
427 92480163468
428 94001445928
429 95543967732
430 97108295342
431 98694389977
432 100302777644
433 101933438627
434 103586939179
435 105263209937
436 106962845037
437 108685807707
438 110432649898
439 112203354801
440 113998516219
441 115818065620
442 117662625894
443 119532162479
444 121427254196
445 123347887490
446 125294684578
447 127267578096
448 129267220630
449 131293580096
450 133347263195
451 135428259821
452 137537221699
453 139674082817
454 141839526481
455 144033523426
456 146256709098
457 148509077260
458 150791310093
459 153103343196
460 155445891699
461 157818929345
462 160223121423
463 162658465830
464 165125676236
465 167624690180
466 170156255578
467 172720349595
468 175317668315
469 177948214108
470 180612733249
471 183311165392
472 186044292437
473 188812095228
474 191615301680
475 194453919052
476 197328727192
477 200239668271
478 203187559225
479 206172384910
480 209194906194
481 212255135478
482 215353887395
483 218491106878
484 221667647035
485 224883497143
486 228139451992
487 231435529619
488 234772580499
489 238150552647
490 241570336569
491 245031926209
492 248536151496
493 252083036431
494 255673468479
495 259307399135
496 262985757372
497 266708542290
498 270476620017
499 274290020928
500 278149670711
501 282055524574
502 286008551281
503 290008755409
504 294057040435
505 298153443595
506 302298929880
507 306493458687
508 310738039737
509 315032683484
510 319378331996
511 323775029690
512 328223782194
513 332724553402
514 337278395248
515 341885324548
516 346546323038
517 351261442888
518 356031731536
519 360857157762
520 365738817064
521 370676732929
522 375671928103
523 380724462907
524 385835427856
525 391004797088
526 396233710849
527 401522199866
528 406871329069
529 412281167414
530 417752849852
531 423286356176
532 428882872834
533 434542438182
534 440266160605
535 446054118262
536 451907491733
537 457826267021
538 463811678063
539 469863771321
540 475983699999
541 482171551848
542 488428554543
543 494754700675
544 501151273051
545 507618326801
546 514157061143
547 520767574077
548 527451141666
549 534207763551
550 541038772891
551 547944233865
552 554925393175
553 561982359544
554 569116458814
555 576327698230
556 583617462607
557 590985825826
558 598434083368
559 605962355243
560 613572018563
561 621263088541
562 629037003240
563 636893846707
564 644834964598
565 652860488863
566 660971849198
567 669169069426
568 677453642268
569 685825662495
570 694286527433
571 702836381438
572 711476708390
573 720207541174
574 729030428684
575 737945477062
576 746954136619
577 756056564863
578 765254301279
579 774547388357
580 783937432781
581 793424552520
582 803010252476
583 812694703866
584 822479503301
585 832364703514
586 842351970410
587 852441434530
588 862634656788
589 872931822758
590 883334587805
591 893843015346
592 904458832240
593 915182182144
594 926014683511
595 936956537018
596 948009458223
597 959173521959
598 970450517582
599 981840602509
600 993345454363
601 1004965289470
602 1016701885325
603 1028555328709
604 1040527473126
605 1052618490491
606 1064830119039
607 1077162591589
608 1089617749123
609 1102195691000
610 1114898336631
611 1127725872968
612 1140680100604
613 1153761269493
614 1166971285764
615 1180310262083
616 1193780185332
617 1207381258338
618 1221115345607
619 1234982714969
620 1248985339469
621 1263123345601
622 1277398789598
623 1291811890796
624 1306364579275
625 1321057141584
626 1335891619255
627 1350868153440
628 1365988871403
629 1381254009723
630 1396665565829
631 1412223845621
632 1427930961010
633 1443787068423
634 1459794367950
635 1475953114248
636 1492265373668
637 1508731472408
638 1525353594445
639 1542131912204
640 1559068700506
641 1576164232712
642 1593420645989
643 1610838287568
644 1628419415294
645 1646164218414
646 1664075048184
647 1682152197610
648 1700397876366
649 1718812453553
650 1737398262802
651 1756155510792
652 1775086627245
653 1794191925537
654 1813473689654
655 1832932311514
656 1852570202242
657 1872387586879
658 1892386975438
659 1912568702497
660 1932935128276
661 1953486668234
662 1974225813035
663 1995152806793
664 2016270241754
665 2037578474636
666 2059079943603
667 2080775088711
668 2102666481993
669 2124754387455
670 2147041481636
671 2169528144112
672 2192216893039
673 2215108193901
674 2238204702052
675 2261506702317
676 2285016957374
677 2308735870706
678 2332666042295
679 2356807963996
680 2381164376552
681 2405735586310
682 2430524444278
683 2455531378670
684 2480759073246
685 2506208047285
686 2531881128774
687 2557778646619
688 2583903542132
689 2610256269191
690 2636839597411
691 2663654074319
692 2690702617348
693 2717985578772
694 2745505992302
695 2773264338529
696 2801263474775
697 2829503977984
698 2857988857014
699 2886718488430
700 2915696000562
701 2944921901528
702 2974399138565
703 3004128318969
704 3034112545129
705 3064352218935
706 3094850565332
707 3125608121129
708 3156627925459
709 3187910617022
710 3219459393966
711 3251274684308
712 3283359811962
713 3315715343355
714 3348344411624
715 3381247688040
716 3414428468513
717 3447887208337
718 3481627332525
719 3515649438165
720 3549956754632
721 3584549986696
722 3619432530396
723 3654604869217
724 3690070531525
725 3725830146230
726 3761887040948
727 3798241955237
728 3834898387399
729 3871856850139
730 3909120977562
731 3946691431320
732 3984571639641
733 4022762377915
734 4061267248972
735 4100086795888
736 4139224760656
737 4178681838953
738 4218461561755
739 4258564741451
740 4298995087792
741 4339753175129
742 4380842855870
743 4422264860752
744 4464022825767
745 4506117601589
746 4548553007049
747 4591329649043
748 4634451492682
749 4677919304922
750 4721736829169
751 4765904955422
752 4810427614127
753 4855305445748
754 4900542530520
755 4946139672899
756 4992100725863
757 5038426620147
758 5085121400109
759 5132185740925
760 5179623840510
761 5227436541848
762 5275627810031
763 5324198617692
764 5373153125529
765 5422492044700
766 5472219693110
767 5522336953681
768 5572847905914
769 5623753565626
770 5675058212420
771 5726762594450
772 5778871152314
773 5831384810021
774 5884307763915
775 5937641074409
776 5991389142330
777 6045552754223
778 6100136475833
779 6155141273536
780 6210571463087
781 6266428150650
782 6322715860988
783 6379435420175
784 6436591521695
785 6494185175696
786 6552220819664
787 6610699607057
788 6669626189035
789 6729001432465
790 6788830161303
791 6849113430615
792 6909855802333
793 6971058478491
794 7032726239247
795 7094859993657
796 7157464698625
797 7220541455673
798 7284094953643
799 7348126444557
800 7412640840312
801 7477639093281
802 7543126296201
803 7609103598322
804 7675575817999
805 7742544258786
806 7810013966803
807 7877985939268
808 7946465407376
809 8015453569510
810 8084955376283
811 8154972184057
812 8225509176070
813 8296567395641
814 8368152215194
815 8440264883781
816 8512910486759
817 8586090434977
818 8659810051424
819 8734070426912
820 8808877078006
821 8884231305695
822 8960138332977
823 9036599626598
824 9113620652074
825 9191202549236
826 9269350981441
827 9348067303289
828 9427356878054
829 9507221229921
830 9587665969858
831 9668692287965
832 9750305997462
833 9832508507958
834 9915305325783
835 9998698034244
836 10082692392416
837 10167289642331
838 10252495749875
839 10338312181204
840 10424744588631
841 10511794615986
842 10599468173534
843 10687766556623
844 10776695886758
845 10866257688314
846 10956457762245
847 11047297814727
848 11138783910024
849 11230917398323
850 11323704559849
851 11417146978591
852 11511250607228
853 11606017215823
854 11701453025600
855 11797559443247
856 11894342910537
857 11991805072889
858 12089952037520
859 12188785640061
860 12288312261806
861 12388533367322
862 12489455563194
863 12591080557803
864 12693414615865
865 12796459640403
866 12900222175616
867 13004703745755
868 13109911125204
869 13215846086978
870 13322515056409
871 13429920005447
872 13538067644471
873 13646959558931
874 13756602694151
875 13866998889598
876 13978154734053
877 14090072270364
878 14202758378082
879 14316214705518
880 14430448372230
881 14545461285663
882 14661260201326
883 14777847234643
884 14895229437487
885 15013408522833
886 15132391787486
887 15252181208833
888 15372783712106
889 15494201487130
890 15616441761403
891 15739506314076
892 15863402622662
893 15988132736160
894 16113703752675
895 16240117938406
896 16367382699494
897 16495499883217
898 16624477150974
899 16754316625192
900 16885025580158
901 17016606360117
902 17149066553328
903 17282408076851
904 17416638779304
905 17551760858507
906 17687781767947
907 17824703932041
908 17962535124346
909 18101277333507
910 18240938598856
911 18381521195271
912 18523032758916
913 18665475796201
914 18808858269325
915 18953182240471
916 19098455942886
917 19244681730624
918 19391867425709
919 19540015618519
920 19689134463397
921 19839226097713
922 19990298952296
923 20142355462189
924 20295403638621
925 20449446158063
926 20604491370211
927 20760541489727
928 20917605148393
929 21075684864206
930 21234788841108
931 21394919843482
932 21556086420053
933 21718290864574
934 21881542013314
935 22045842469344
936 22211200632525
937 22377619357435
938 22545107395206
939 22713667120633
940 22883307578172
941 23054031457775
942 23225847358905
943 23398758228307
944 23572773023062
945 23747894201114
946 23924131018501
947 24101486254336
948 24279968711060
949 24459581429714
950 24640333577035
951 24822227695910
952 25005273257837
953 25189473133050
954 25374836330514
955 25561365987851
956 25749071484858
957 25937955451628
958 26128027578691
959 26319290829523
960 26511754423324
961 26705421596266
962 26900301945093
963 27096398189053
964 27293720241446
965 27492271161269
966 27692060381360
967 27893091238889
968 28095373551124
969 28298910128573
970 28503711111218
971 28709779655535
972 28917125411891
973 29125751820581
974 29335668923145
975 29546879623619
976 29759394292262
977 29973216185472
978 30188355174723
979 30404814805725
980 30622605348208
981 30841729801677
982 31062198770763
983 31284015613903
984 31507190427428
985 31731726864913
986 31957635427882
987 32184919213740
988 32413589065266
989 32643648445217
990 32875107678703
991 33107970529289
992 33342247734396
993 33577942491431
994 33815065885273
995 34053621485442
996 34293619849431
997 34535064853413
998 34777967474490
999 35022331012337