0 1
1 1
2 0
3 0
4 1
5 0
6 1
7 0
8 1
9 0
10 1
11 1
12 1
13 1
14 2
15 1
16 2
17 1
18 2
19 2
20 3
21 2
22 3
23 2
24 4
25 3
26 4
27 3
28 5
29 4
30 5
31 5
32 6
33 5
34 8
35 6
36 9
37 6
38 9
39 8
40 11
41 10
42 12
43 11
44 14
45 12
46 16
47 13
48 18
49 16
50 20
51 18
52 22
53 20
54 25
55 23
56 29
57 25
58 31
59 29
60 36
61 33
62 39
63 36
64 45
65 40
66 49
67 45
68 54
69 51
70 61
71 58
72 66
73 63
74 75
75 70
76 84
77 77
78 91
79 86
80 101
81 97
82 110
83 106
84 124
85 118
86 135
87 128
88 149
89 143
90 164
91 159
92 179
93 172
94 198
95 191
96 217
97 209
98 237
99 231
100 260
101 254
102 283
103 277
104 313
105 304
106 342
107 330
108 371
109 365
110 405
111 400
112 442
113 435
114 482
115 475
116 527
117 515
118 572
119 565
120 624
121 616
122 674
123 669
124 737
125 729
126 801
127 791
128 866
129 861
130 942
131 937
132 1020
133 1015
134 1108
135 1100
136 1201
137 1192
138 1296
139 1296
140 1407
141 1406
142 1516
143 1517
144 1646
145 1643
146 1779
147 1774
148 1920
149 1920
150 2072
151 2080
152 2233
153 2242
154 2416
155 2422
156 2604
157 2609
158 2804
159 2818
160 3026
161 3042
162 3253
163 3272
164 3508
165 3528
166 3775
167 3795
168 4060
169 4092
170 4364
171 4403
172 4691
173 4730
174 5047
175 5089
176 5424
177 5461
178 5817
179 5877
180 6248
181 6316
182 6700
183 6774
184 7194
185 7270
186 7717
187 7794
188 8270
189 8367
190 8865
191 8971
192 9490
193 9612
194 10171
195 10300
196 10897
197 11026
198 11651
199 11813
200 12476
201 12647
202 13339
203 13527
204 14276
205 14470
206 15260
207 15470
208 16305
209 16550
210 17427
211 17695
212 18604
213 18893
214 19883
215 20184
216 21232
217 21549
218 22651
219 23011
220 24175
221 24570
222 25776
223 26208
224 27510
225 27960
226 29328
227 29805
228 31259
229 31791
230 33317
231 33893
232 35490
233 36101
234 37812
235 38472
236 40271
237 40965
238 42868
239 43637
240 45631
241 46460
242 48550
243 49434
244 51677
245 52610
246 54968
247 55952
248 58442
249 59532
250 62141
251 63313
252 66048
253 67297
254 70202
255 71528
256 74606
257 75995
258 79238
259 80763
260 84167
261 85786
262 89352
263 91093
264 94882
265 96727
266 100717
267 102662
268 106863
269 108973
270 113392
271 115641
272 120273
273 122665
274 127582
275 130107
276 135287
277 137966
278 143405
279 146303
280 152027
281 155102
282 161080
283 164360
284 170716
285 174169
286 180860
287 184509
288 191547
289 195463
290 202848
291 207027
292 214760
293 219194
294 227382
295 232069
296 240669
297 245613
298 254673
299 259964
300 269479
301 275094
302 285049
303 290995
304 301534
305 307824
306 318881
307 325528
308 337159
309 344247
310 356437
311 363955
312 376744
313 384692
314 398195
315 406588
316 420777
317 429606
318 444509
319 453949
320 469569
321 479555
322 495922
323 506478
324 523730
325 534868
326 552995
327 564719
328 583770
329 596233
330 616193
331 629364
332 650274
333 664202
334 686221
335 700908
336 724028
337 739485
338 763724
339 780137
340 805580
341 822885
342 849523
343 867802
344 895839
345 915068
346 944485
347 964751
348 995596
349 1017071
350 1049392
351 1072037
352 1105866
353 1129740
354 1165338
355 1190462
356 1227799
357 1254219
358 1293360
359 1321294
360 1362305
361 1391770
362 1434662
363 1465712
364 1510814
365 1543453
366 1590692
367 1625025
368 1674568
369 1710804
370 1762691
371 1800853
372 1855141
373 1895290
374 1952296
375 1994537
376 2054252
377 2098628
378 2161186
379 2208005
380 2273471
381 2322722
382 2391241
383 2443024
384 2514941
385 2569348
386 2644636
387 2701749
388 2780613
389 2840822
390 2923311
391 2986629
392 3072916
393 3139435
394 3229898
395 3299754
396 3394491
397 3467777
398 3566938
399 3644097
400 3747834
401 3828850
402 3937306
403 4022451
404 4136097
405 4225437
406 4344365
407 4438065
408 4562476
409 4661029
410 4791155
411 4894588
412 5030634
413 5139184
414 5281656
415 5395491
416 5544524
417 5663894
418 5819735
419 5945180
420 6108114
421 6239695
422 6409900
423 6547930
424 6726185
425 6870817
426 7057185
427 7208765
428 7403600
429 7562696
430 7766313
431 7933170
432 8145846
433 8320763
434 8543292
435 8726525
436 8959087
437 9150984
438 9394066
439 9595375
440 9849335
441 10060256
442 10325454
443 10546397
444 10823764
445 11055165
446 11344887
447 11587137
448 11889856
449 12143779
450 12459852
451 12725803
452 13055852
453 13334258
454 13679280
455 13970670
456 14330992
457 14635834
458 15012117
459 15331559
460 15724375
461 16058709
462 16468688
463 16818574
464 17246900
465 17612898
466 18060139
467 18442873
468 18909796
469 19310529
470 19797780
471 20216954
472 20725390
473 21163881
474 21694816
475 22153339
476 22707479
477 23186747
478 23764987
479 24266512
480 24869873
481 25394207
482 26023548
483 26571742
484 27228757
485 27801606
486 28487055
487 29085737
488 29800773
489 30426862
490 31172648
491 31826945
492 32604572
493 33288309
494 34099850
495 34814071
496 35660519
497 36406483
498 37289171
499 38068864
500 38989224
501 39803752
502 40763121
503 41613923
504 42614718
505 43503095
506 44546430
507 45473956
508 46561805
509 47530710
510 48664593
511 49676324
512 50857976
513 51914173
514 53146362
515 54248904
516 55533117
517 56683763
518 58022177
519 59223661
520 60618271
521 61872250
522 63325282
523 64633908
524 66148551
525 67513904
526 69092033
527 70516326
528 72160582
529 73647254
530 75359958
531 76910991
532 78694930
533 80312850
534 82171622
535 83859113
536 85795367
537 87554991
538 89571740
539 91407527
540 93507723
541 95422098
542 97608914
543 99605283
544 101883171
545 103964498
546 106336467
547 108506105
548 110975833
549 113238366
550 115809690
551 118168200
552 120844887
553 123303332
554 126090530
555 128652606
556 131554147
557 134224058
558 137244246
559 140027434
560 143170878
561 146071035
562 149342222
563 152364172
564 155769587
565 158917782
566 162461760
567 165741248
568 169429247
569 172846300
570 176683648
571 180243338
572 184235579
573 187943352
574 192097974
575 195959386
576 200281748
577 204302807
578 208799630
579 212987861
580 217665617
581 222026878
582 226892142
583 231433230
584 236494858
585 241222674
586 246487180
587 251408849
588 256884264
589 262008714
590 267702599
591 273037022
592 278957936
593 284510315
594 290668309
595 296447070
596 302850233
597 308863759
598 315521576
599 321780948
600 328702674
601 335216323
602 342411868
603 349189580
604 356671054
605 363722716
606 371500128
607 378836106
608 386920683
609 394553709
610 402956599
611 410897012
612 419630140
613 427890056
614 436967540
615 445558716
616 454992764
617 463927510
618 473731281
619 483024901
620 493212361
621 502877130
622 513462248
623 523512621
624 534512300
625 544962338
626 556390935
627 567256021
628 579129622
629 590427332
630 602762231
631 614507793
632 627320792
633 639531181
634 652842709
635 665534944
636 679362122
637 692554344
638 706916203
639 720629357
640 735545616
641 749798301
642 765288835
643 780101356
644 796190228
645 811582811
646 828290465
647 844284883
648 861634732
649 878255700
650 896270690
651 913540477
652 932244825
653 950187383
654 969609098
655 988249579
656 1008413374
657 1027777143
658 1048710596
659 1068827158
660 1090557770
661 1111453666
662 1134010625
663 1155714603
664 1179131022
665 1201672564
666 1225977839
667 1249387597
668 1274614562
669 1298927759
670 1325109166
671 1350357365
672 1377527910
673 1403745387
674 1431943760
675 1459165779
676 1488428219
677 1516690993
678 1547055809
679 1576401112
680 1607907602
681 1638372830
682 1671062032
683 1702688860
684 1736606684
685 1769436603
686 1804625640
687 1838702095
688 1875208226
689 1910580106
690 1948450457
691 1985162876
692 2024445981
693 2062547806
694 2103297861
695 2142838665
696 2185106458
697 2226138564
698 2269978199
699 2312559073
700 2358026711
701 2402209899
702 2449362702
703 2495206593
704 2544109486
705 2591672640
706 2642385470
707 2691729908
708 2744317183
709 2795510595
710 2850038346
711 2903145550
712 2959682165
713 3014771485
714 3073392728
715 3130534380
716 3191311513
717 3250578533
718 3313588715
719 3375061197
720 3440382416
721 3504136908
722 3571849907
723 3637967600
724 3708161982
725 3776726635
726 3849486606
727 3920584769
728 3996001471
729 4069727292
730 4147892847
731 4224337316
732 4305348528
733 4384607627
734 4468568934
735 4550741755
736 4637753763
737 4722942273
738 4813112002
739 4901428738
740 4994865486
741 5086417232
742 5183234904
743 5278135629
744 5378457292
745 5476823954
746 5580769278
747 5682722777
748 5790418152
749 5896090039
750 6007664305
751 6117181675
752 6232769406
753 6346267492
754 6466013341
755 6583630015
756 6707675360
757 6829553516
758 6958046803
759 7084341365
760 7217436547
761 7348297337
762 7486151985
763 7621738821
764 7764523449
765 7904998578
766 8052879777
767 8198413377
768 8351566525
769 8502339860
770 8660945437
771 8817136099
772 8981380492
773 9143176150
774 9313260336
775 9480853170
776 9656973300
777 9830562865
778 10012925531
779 10192725141
780 10381543053
781 10567763454
782 10763255603
783 10956117430
784 11158519984
785 11358249365
786 11567792811
787 11774625412
788 11991554559
789 12205740288
790 12430304516
791 12652091640
792 12884549284
793 13114197254
794 13354824374
795 13592601273
796 13841670248
797 14087851893
798 14345649278
799 14600530071
800 14867349385
801 15131220842
802 15407367121
803 15680534763
804 15966331158
805 16249109512
806 16544876037
807 16837589801
808 17143663609
809 17446658914
810 17763384293
811 18077004094
812 18404739126
813 18729341967
814 19068464892
815 19404420600
816 19755309633
817 20102999483
818 20466048581
819 20825877993
820 21201492622
821 21573863938
822 21962463244
823 22347800047
824 22749827426
825 23148562170
826 23564460820
827 23977041819
828 24407274039
829 24834175596
830 25279217971
831 25720913109
832 26181257139
833 26638241139
834 27114405155
835 27587186362
836 28079690388
837 28568795633
838 29078181233
839 29584164980
840 30110990473
841 30634407813
842 31179248038
843 31720679622
844 32284143752
845 32844184637
846 33426880198
847 34006148043
848 34608709958
849 35207852336
850 35830933725
851 36450603887
852 37094878425
853 37735754791
854 38401932584
855 39064713018
856 39753506567
857 40438913000
858 41151066313
859 41859856866
860 42596133437
861 43329071398
862 44090259417
863 44848139079
864 45635067922
865 46418707859
866 47232210403
867 48042454436
868 48883400815
869 49721133866
870 50590415560
871 51456531750
872 52355072963
873 53250499992
874 54179266976
875 55104961645
876 56064929232
877 57021877541
878 58014060588
879 59003298479
880 60028739976
881 61051310355
882 62111087772
883 63168076212
884 64263316880
885 65355839824
886 66487684761
887 67616894606
888 68786527589
889 69953631336
890 71162269251
891 72368485883
892 73617387176
893 74863985413
894 76154463084
895 77442746170
896 78776131740
897 80107444063
898 81485117704
899 82860866487
900 84284251143
901 85705859019
902 87176419539
903 88645366049
904 90164633839
905 91682437998
906 93251964369
907 94820198460
908 96441592955
909 98061893332
910 99736813072
911 101410840360
912 103140992990
913 104870470886
914 106657640731
915 108444340747
916 110290335753
917 112136087753
918 114042781877
919 115949492341
920 117918815889
921 119888422060
922 121922363470
923 123956871957
924 126057506538
925 128158980955
926 130328412676
927 132498984309
928 134739399241
929 136981284765
930 139294926443
931 141610382432
932 143999566265
933 146390926796
934 148858064370
935 151327735567
936 153875276502
937 156425736082
938 159056220224
939 161690046834
940 164406085280
941 167125903010
942 169930190444
943 172738716016
944 175634053126
945 178534082298
946 181523318024
947 184517732855
948 187603819465
949 190695619153
950 193881590253
951 197073825077
952 200362812746
953 203658639477
954 207053893822
955 210456563357
956 213961399872
957 217474259925
958 221092105014
959 224718637482
960 228453016441
961 232196765276
962 236051313038
963 239915949744
964 243894440082
965 247883736541
966 251990016569
967 256107863231
968 260345910803
969 264596345777
970 268970256424
971 273357396211
972 277871387104
973 282399491066
974 287057937614
975 291731384696
976 296538752892
977 301362060402
978 306322963039
979 311300813539
980 316420000698
981 321557170164
982 326839531922
983 332140961358
984 337591574322
985 343062342458
986 348686381477
987 354331726444
988 360134542047
989 365959888711
990 371946984501
991 377957878273
992 384134923389
993 390337087154
994 396709959326
995 403109282086
996 409683979567
997 416286530658
998 423069254859
999 429881318939
1000 436878445301