0 1
1 0
2 0
3 1
4 1
5 1
6 1
7 0
8 1
9 1
10 1
11 1
12 2
13 2
14 1
15 3
16 2
17 2
18 3
19 3
20 4
21 4
22 3
23 4
24 6
25 5
26 5
27 7
28 7
29 7
30 9
31 8
32 9
33 11
34 10
35 12
36 14
37 13
38 14
39 17
40 18
41 18
42 20
43 21
44 23
45 27
46 25
47 27
48 33
49 32
50 34
51 39
52 39
53 42
54 46
55 48
56 51
57 56
58 57
59 61
60 71
61 69
62 72
63 83
64 85
65 90
66 97
67 99
68 108
69 117
70 119
71 126
72 140
73 143
74 149
75 167
76 170
77 178
78 194
79 200
80 215
81 229
82 233
83 250
84 272
85 280
86 291
87 316
88 329
89 344
90 371
91 382
92 404
93 434
94 445
95 473
96 507
97 520
98 547
99 588
100 612
101 638
102 678
103 706
104 744
105 793
106 814
107 857
108 919
109 947
110 993
111 1056
112 1095
113 1148
114 1214
115 1264
116 1325
117 1400
118 1450
119 1521
120 1620
121 1669
122 1742
123 1852
124 1922
125 2011
126 2115
127 2194
128 2305
129 2426
130 2514
131 2629
132 2776
133 2877
134 2999
135 3171
136 3286
137 3426
138 3605
139 3742
140 3919
141 4108
142 4250
143 4449
144 4680
145 4850
146 5048
147 5306
148 5513
149 5741
150 6022
151 6242
152 6515
153 6828
154 7069
155 7383
156 7735
157 8008
158 8342
159 8741
160 9076
161 9436
162 9862
163 10239
164 10668
165 11154
166 11541
167 12020
168 12582
169 13026
170 13552
171 14158
172 14678
173 15267
174 15924
175 16520
176 17181
177 17913
178 18557
179 19301
180 20155
181 20854
182 21657
183 22603
184 23423
185 24333
186 25330
187 26244
188 27287
189 28403
190 29410
191 30543
192 31814
193 32938
194 34174
195 35599
196 36856
197 38233
198 39772
199 41185
200 42767
201 44441
202 45977
203 47729
204 49634
205 51362
206 53233
207 55338
208 57298
209 59385
210 61689
211 63830
212 66186
213 68730
214 71075
215 73702
216 76522
217 79123
218 81979
219 85105
220 88060
221 91180
222 94574
223 97843
224 101359
225 105128
226 108649
227 112528
228 116737
229 120651
230 124898
231 129487
232 133869
233 138556
234 143562
235 148430
236 153612
237 159123
238 164428
239 170152
240 176316
241 182115
242 188349
243 195120
244 201609
245 208505
246 215811
247 222955
248 230618
249 238667
250 246492
251 254854
252 263776
253 272388
254 281512
255 291341
256 300834
257 310862
258 321547
259 332009
260 343152
261 354801
262 366199
263 378420
264 391318
265 403881
266 417112
267 431239
268 445130
269 459668
270 475075
271 490234
272 506278
273 523142
274 539686
275 557304
276 575795
277 593929
278 613094
279 633351
280 653394
281 674286
282 696304
283 718246
284 741269
285 765395
286 789180
287 814351
288 840849
289 866915
290 894344
291 923180
292 951830
293 981804
294 1013168
295 1044546
296 1077336
297 1111571
298 1145694
299 1181528
300 1219116
301 1256274
302 1295210
303 1336192
304 1376983
305 1419539
306 1463912
307 1508420
308 1555014
309 1603425
310 1651865
311 1702524
312 1755466
313 1808289
314 1863341
315 1921076
316 1978724
317 2038706
318 2101335
319 2164204
320 2229829
321 2297849
322 2366101
323 2437528
324 2511828
325 2586242
326 2663575
327 2744378
328 2825613
329 2909807
330 2997505
331 3085722
332 3177544
333 3272863
334 3368617
335 3468531
336 3572206
337 3676324
338 3784620
339 3897299
340 4010864
341 4128345
342 4250400
343 4373783
344 4501752
345 4634376
346 4767890
347 4906816
348 5051063
349 5196127
350 5346704
351 5502985
352 5660784
353 5824173
354 5993404
355 6164764
356 6342133
357 6525636
358 6711155
359 6903563
360 7102997
361 7303961
362 7512157
363 7728253
364 7946619
365 8172407
366 8405852
367 8642502
368 8887540
369 9140478
370 9396618
371 9661746
372 9936058
373 10213503
374 10500227
375 10797310
376 11097922
377 11408319
378 11729312
379 12054840
380 12391410
381 12738396
382 13090186
383 13454294
384 13830220
385 14211025
386 14604010
387 15010476
388 15422892
389 15847964
390 16286986
391 16732600
392 17192681
393 17667138
394 18148414
395 18645824
396 19158704
397 19678847
398 20215645
399 20769763
400 21332594
401 21912082
402 22509818
403 23117741
404 23744331
405 24389907
406 25045330
407 25721784
408 26419277
409 27127049
410 27856706
411 28608941
412 29373579
413 30160949
414 30971884
415 31797214
416 32646978
417 33521648
418 34411211
419 35327866
420 36272122
421 37231096
422 38218688
423 39236615
424 40271667
425 41336631
426 42432410
427 43548164
428 44696837
429 45877814
430 47079701
431 48316896
432 49590118
433 50885141
434 52217178
435 53588824
436 54984304
437 56418978
438 57894965
439 59398067
440 60944262
441 62532750
442 64150140
443 65814634
444 67525712
445 69267195
446 71056993
447 72898276
448 74773651
449 76699848
450 78680056
451 80697324
452 82770766
453 84900775
454 87069932
455 89300467
456 91591713
457 93924737
458 96322080
459 98785839
460 101296256
461 103873065
462 106520172
463 109218998
464 111990463
465 114835890
466 117734582
467 120712982
468 123771869
469 126887177
470 130086328
471 133371697
472 136720242
473 140156912
474 143684434
475 147281788
476 150973605
477 154761737
478 158623485
479 162588033
480 166657349
481 170803013
482 175057616
483 179425726
484 183878223
485 188445581
486 193130911
487 197909728
488 202813031
489 207840901
490 212967726
491 218227754
492 223623646
493 229124124
494 234765222
495 240553484
496 246454664
497 252505026
498 258710350
499 265039511
500 271530224
501 278182637
502 284967012
503 291925844
504 299059890
505 306333826
506 313789930
507 321436229
508 329235068
509 337226519
510 345418767
511 353775240
512 362340758
513 371118113
514 380069776
515 389247034
516 398650864
517 408240490
518 418068123
519 428140384
520 438414870
521 448938645
522 459721814
523 470724419
524 481996128
525 493542062
526 505318283
527 517385438
528 529747818
529 542354801
530 555269293
531 568499095
532 581995381
533 595816555
534 609971268
535 624414744
536 639205297
537 654349737
538 669800141
539 685624097
540 701828829
541 718355471
542 735278318
543 752610065
544 770290479
545 788390074
546 806919175
547 825826351
548 845183663
549 864995702
550 885208895
551 905902367
552 927085630
553 948694265
554 970811277
555 993454005
556 1016552636
557 1040190683
558 1064384431
559 1089070195
560 1114334816
561 1140184188
562 1166557069
563 1193550207
564 1221170954
565 1249347377
566 1278176599
567 1307680031
568 1337781504
569 1368574361
570 1400080698
571 1432226880
572 1465115599
573 1498759072
574 1533081891
575 1568199918
576 1604122540
577 1640767854
578 1678254298
579 1716602485
580 1755727618
581 1795739194
582 1836664546
583 1878423960
584 1921132599
585 1964808686
586 2009365463
587 2054939415
588 2101547846
589 2149091392
590 2197711637
591 2247433525
592 2298160911
593 2350027741
594 2403061118
595 2457172906
596 2512498137
597 2569060474
598 2626766274
599 2685769130
600 2746094103
601 2807627462
602 2870535981
603 2934855979
604 3000471440
605 3067542958
606 3136103454
607 3206053499
608 3277557845
609 3350639226
610 3425194594
611 3501403618
612 3579298546
613 3658756490
614 3739965526
615 3822973573
616 3907648502
617 3994179908
618 4082614884
619 4172833266
620 4265032274
621 4359240766
622 4455343113
623 4553556815
624 4653914356
625 4756280632
626 4860875725
627 4967758938
628 5076788121
629 5188177639
630 5301989181
631 5418086598
632 5536702650
633 5657881919
634 5781485593
635 5907772764
636 6036784456
637 6168369807
638 6302794682
639 6440122338
640 6580197396
641 6723271321
642 6869420590
643 7018500476
644 7170774830
645 7326304603
646 7484933461
647 7646966271
648 7812464042
649 7981247930
650 8153634423
651 8329700907
652 8509274895
653 8692661102
654 8879942568
655 9070962902
656 9266031765
657 9465226753
658 9668382866
659 9875846487
660 10087699701
661 10303742349
662 10524346820
663 10749618435
664 10979354115
665 11213917528
666 11453410512
667 11697661240
668 11947044199
669 12201644559
670 12461285457
671 12726372587
672 12997010036
673 13272986497
674 13554726148
675 13842364384
676 14135675540
677 14435088792
678 14740741050
679 15052430487
680 15370603752
681 15695367774
682 16026530141
683 16364578670
684 16709629724
685 17061457489
686 17420559015
687 17787101870
688 18160850103
689 18542294092
690 18931609094
691 19328573432
692 19733714187
693 20147179195
694 20568744408
695 20998989483
696 21438060169
697 21885712152
698 22342542436
699 22808740962
700 23284058274
701 23769070814
702 24263995418
703 24768605692
704 25283505522
705 25808887768
706 26344509276
707 26891052500
708 27448715354
709 28017217254
710 28597267367
711 29189099011
712 29792445665
713 30408001434
714 31036014762
715 31676252314
716 32329424324
717 32995773268
718 33675054985
719 34368052524
720 35075021958
721 35795661198
722 36530805647
723 37280759669
724 38045220555
725 38825015124
726 39620448665
727 40431278483
728 41258358912
729 42101971482
730 42961869872
731 43838973575
732 44733603442
733 45645457483
734 46575496457
735 47524104758
736 48490961804
737 49477044370
738 50482747783
739 51507800345
740 52553219415
741 53619355672
742 54705959380
743 55814131927
744 56944249024
745 58096008326
746 59270539055
747 60468315637
748 61689025822
749 62933797188
750 64203127249
751 65496738592
752 66815833634
753 68160871373
754 69531578348
755 70929262524
756 72354390774
757 73806660607
758 75287423740
759 76797236474
760 78335796642
761 79904433488
762 81503760764
763 83133527920
764 84795126297
765 86489139037
766 88215297731
767 89975145560
768 91769287965
769 93597400917
770 95461089926
771 97361038028
772 99296955837
773 101270438422
774 103282209384
775 105332050602
776 107421603621
777 109551594028
778 111721798408
779 113934004020
780 116188976044
781 118486404067
782 120828183605
783 123215182384
784 125647103101
785 128125845073
786 130652296535
787 133226279057
788 135849761176
789 138523606995
790 141247647860
791 144023989850
792 146853582812
793 149736178016
794 152673975753
795 155668057654
796 158718162180
797 161826538094
798 164994308234
799 168221315589
800 171509904435
801 174861143070
802 178274930458
803 181753784558
804 185298840446
805 188909925989
806 192589636324
807 196339301377
808 200158754822
809 204050616339
810 208016282041
811 212055671970
812 216171563186
813 220365312407
814 224636870777
815 228989230756
816 233423793178
817 237940481536
818 242542397906
819 247231128632
820 252006625286
821 256871986521
822 261828927210
823 266877518902
824 272021003452
825 277261075333
826 282597807596
827 288034740527
828 293573643109
829 299214523107
830 304961068237
831 310815221202
832 316777080405
833 322850357276
834 329037102880
835 335337574820
836 341755610575
837 348293301309
838 354950933883
839 361732643233
840 368640631299
841 375675075867
842 382840343094
843 390138858170
844 397570862404
845 405140778013
846 412851114750
847 420702359554
848 428699107502
849 436843874911
850 445137211418
851 453584006925
852 462186973414
853 470946571604
854 479867910555
855 488953983795
856 498205283326
857 507627057550
858 517222429164
859 526992122952
860 536941614851
861 547073995750
862 557390138664
863 567895886043
864 578594505430
865 589486806363
866 600578836007
867 611874258335
868 623373956274
869 635084090724
870 647008508226
871 659148308332
872 671509993648
873 684097416666
874 696911798033
875 709960089642
876 723246298544
877 736771665235
878 750543414320
879 764565949868
880 778840636068
881 793374782127
882 808173091006
883 823237213283
884 838574794186
885 854190589260
886 870086338399
887 886270288443
888 902747415805
889 919519435587
890 936594947247
891 953979323832
892 971674522303
893 989689289509
894 1008029283890
895 1026696830934
896 1045701006584
897 1065047638370
898 1084739205039
899 1104785404600
900 1125192364607
901 1145962488457
902 1167105983598
903 1188629476541
904 1210535589946
905 1232834753661
906 1255533864521
907 1278636074838
908 1302152243500
909 1326089405975
910 1350450944599
911 1375248362967
912 1400489157532
913 1426176691276
914 1452322985095
915 1478936154528
916 1506019756080
917 1533586193769
918 1561643952419
919 1590197125179
920 1619258662224
921 1648837153980
922 1678937088337
923 1709572206339
924 1740751559356
925 1772479685258
926 1804770851917
927 1837634945647
928 1871076795808
929 1905111045778
930 1939748069569
931 1974993240584
932 2010861965796
933 2047364819120
934 2084507559078
935 2122306553768
936 2160772839230
937 2199912391176
938 2239742251885
939 2280274331967
940 2321515015994
941 2363481715438
942 2406187053306
943 2449638109159
944 2493853091596
945 2538844938442
946 2584621105061
947 2631201048200
948 2678598317070
949 2726820555075
950 2775888066626
951 2825815321921
952 2876610605216
953 2928294737713
954 2980882928478
955 3034384334684
956 3088820614984
957 3144207526942
958 3200554753929
959 3257885289662
960 3316215680811
961 3375555769394
962 3435929700817
963 3497355160466
964 3559842649294
965 3623417005644
966 3688096687413
967 3753893380771
968 3820832980516
969 3888934503911
970 3958210343773
971 4028687830712
972 4100387088114
973 4173320816696
974 4247517577770
975 4322998890161
976 4399778137798
977 4477884896904
978 4557341684072
979 4638163147918
980 4720380179118
981 4804015872471
982 4889085913491
983 4975622936783
984 5063651218334
985 5153186933816
986 5244264043619
987 5336908638656
988 5431137809822
989 5526986602631
990 5624482374247
991 5723643574990
992 5824506993582
993 5927100798748
994 6031444547577
995 6137577132644
996 6245527996149
997 6355317535471
998 6466986295739
999 6580565691969
1000 6696077314110