0 1
1 0
2 1
3 1
4 1
5 2
6 1
7 3
8 2
9 4
10 3
11 5
12 5
13 6
14 7
15 7
16 10
17 9
18 12
19 12
20 15
21 15
22 18
23 19
24 22
25 24
26 26
27 30
28 32
29 36
30 39
31 43
32 48
33 51
34 57
35 61
36 68
37 73
38 79
39 87
40 93
41 103
42 108
43 121
44 127
45 140
46 148
47 162
48 173
49 187
50 200
51 215
52 232
53 247
54 266
55 283
56 306
57 324
58 348
59 371
60 397
61 423
62 450
63 480
64 512
65 543
66 579
67 614
68 655
69 693
70 737
71 781
72 830
73 879
74 930
75 987
76 1044
77 1105
78 1168
79 1236
80 1307
81 1381
82 1456
83 1541
84 1625
85 1714
86 1808
87 1905
88 2011
89 2116
90 2230
91 2347
92 2473
93 2600
94 2734
95 2877
96 3024
97 3180
98 3337
99 3509
100 3684
101 3868
102 4057
103 4260
104 4467
105 4686
106 4910
107 5149
108 5397
109 5653
110 5921
111 6200
112 6494
113 6796
114 7110
115 7441
116 7784
117 8140
118 8508
119 8896
120 9300
121 9715
122 10149
123 10600
124 11073
125 11558
126 12065
127 12592
128 13143
129 13709
130 14300
131 14913
132 15555
133 16213
134 16899
135 17612
136 18354
137 19123
138 19913
139 20747
140 21602
141 22492
142 23410
143 24367
144 25362
145 26385
146 27448
147 28551
148 29698
149 30879
150 32105
151 33375
152 34695
153 36055
154 37463
155 38924
156 40442
157 42004
158 43619
159 45300
160 47034
161 48830
162 50681
163 52604
164 54594
165 56643
166 58765
167 60962
168 63237
169 65582
170 68003
171 70512
172 73106
173 75783
174 78542
175 81402
176 84360
177 87404
178 90550
179 93805
180 97169
181 100636
182 104209
183 107909
184 111729
185 115664
186 119726
187 123921
188 128256
189 132719
190 137321
191 142079
192 146986
193 152047
194 157250
195 162638
196 168188
197 173909
198 179800
199 185884
200 192161
201 198617
202 205271
203 212138
204 219221
205 226504
206 234013
207 241748
208 249735
209 257942
210 266402
211 275116
212 284101
213 293344
214 302849
215 312662
216 322758
217 333152
218 343839
219 354854
220 366206
221 377864
222 389874
223 402233
224 414963
225 428047
226 441504
227 455369
228 469630
229 484301
230 499370
231 514896
232 530864
233 547281
234 564151
235 581518
236 599380
237 617734
238 636598
239 656003
240 675975
241 696467
242 717545
243 739208
244 761491
245 784374
246 807884
247 832060
248 856904
249 882425
250 908627
251 935575
252 963261
253 991687
254 1020875
255 1050870
256 1081693
257 1113336
258 1145809
259 1179196
260 1213471
261 1248654
262 1284768
263 1321867
264 1359967
265 1399059
266 1439178
267 1480378
268 1522682
269 1566085
270 1610620
271 1656341
272 1703278
273 1751415
274 1800809
275 1851499
276 1903546
277 1956899
278 2011635
279 2067808
280 2125446
281 2184550
282 2245160
283 2307352
284 2371148
285 2436551
286 2503619
287 2572416
288 2642988
289 2715324
290 2789474
291 2865531
292 2943518
293 3023464
294 3105390
295 3189406
296 3275550
297 3363814
298 3454275
299 3547024
300 3642098
301 3739509
302 3839310
303 3941621
304 4046473
305 4153894
306 4263942
307 4376729
308 4492297
309 4610673
310 4731928
311 4856175
312 4983476
313 5113851
314 5247349
315 5384137
316 5524261
317 5667736
318 5814667
319 5965157
320 6119304
321 6277105
322 6438674
323 6604154
324 6773607
325 6947069
326 7124636
327 7306465
328 7492630
329 7683195
330 7878234
331 8077914
332 8282338
333 8491530
334 8705616
335 8924780
336 9149110
337 9378643
338 9613517
339 9853896
340 10099934
341 10351626
342 10609154
343 10872689
344 11142341
345 11418195
346 11700376
347 11989128
348 12284531
349 12586704
350 12895747
351 13211911
352 13535363
353 13866134
354 14204433
355 14550456
356 14904395
357 15266304
358 15636388
359 16014904
360 16402015
361 16797794
362 17202449
363 17616262
364 18039403
365 18471990
366 18914235
367 19366415
368 19828716
369 20301297
370 20784333
371 21278188
372 21783048
373 22299036
374 22826396
375 23365463
376 23916493
377 24479619
378 25055080
379 25643268
380 26244391
381 26858624
382 27486265
383 28127695
384 28783165
385 29452856
386 30137080
387 30836216
388 31550605
389 32280414
390 33025978
391 33787706
392 34565930
393 35360852
394 36172846
395 37002356
396 37849767
397 38715243
398 39599181
399 40502119
400 41424372
401 42366253
402 43328110
403 44310519
404 45313810
405 46338331
406 47384495
407 48452869
408 49543901
409 50657849
410 51795218
411 52956571
412 54142414
413 55353098
414 56589064
415 57850994
416 59139377
417 60454565
418 61797117
419 63167756
420 64566958
421 65995133
422 67452857
423 68940870
424 70459759
425 72009963
426 73592113
427 75206940
428 76855112
429 78537052
430 80253514
431 82005243
432 83792980
433 85617204
434 87478561
435 89378053
436 91316348
437 93294039
438 95311851
439 97370766
440 99471504
441 101614699
442 103801204
443 106032014
444 108307958
445 110629677
446 112998047
447 115414174
448 117878933
449 120393089
450 122957542
451 125573399
452 128241678
453 130963117
454 133738736
455 136569809
456 139457349
457 142402134
458 145405272
459 148468080
460 151591689
461 154776981
462 158025121
463 161337482
464 164715227
465 168159367
466 171671160
467 175252111
468 178903424
469 182626222
470 186421745
471 190291594
472 194237231
473 198259712
474 202360485
475 206541206
476 210803349
477 215148129
478 219577087
479 224092082
480 228694603
481 233385959
482 238167762
483 243041986
484 248010285
485 253074103
486 258235212
487 263495546
488 268856934
489 274320972
490 279889441
491 285564600
492 291348340
493 297242253
494 303248338
495 309368908
496 315606114
497 321961671
498 328437704
499 335036669
500 341760734
501 348611800
502 355592207
503 362704607
504 369951252
505 377334216
506 384855944
507 392519153
508 400326502
509 408280148
510 416382635
511 424636939
512 433045702
513 441611366
514 450336639
515 459224793
516 468278636
517 477500681
518 486893792
519 496461495
520 506206796
521 516132435
522 526241556
523 536537723
524 547024104
525 557703750
526 568580054
527 579656754
528 590937437
529 602425092
530 614123331
531 626036217
532 638167526
533 650520667
534 663099329
535 675907874
536 688950268
537 702230074
538 715751428
539 729518991
540 743536954
541 757808981
542 772339601
543 787133576
544 802195538
545 817529636
546 833140443
547 849033078
548 865212380
549 881682774
550 898449253
551 915517306
552 932892070
553 950578248
554 968580910
555 986906153
556 1005559425
557 1024545785
558 1043870752
559 1063540606
560 1083561061
561 1103937500
562 1124676095
563 1145783343
564 1167265490
565 1189128189
566 1211377783
567 1234021378
568 1257065596
569 1280516679
570 1304381287
571 1328666739
572 1353380237
573 1378528248
574 1404118039
575 1430157613
576 1456654477
577 1483615429
578 1511048143
579 1538961192
580 1567362494
581 1596259595
582 1625660588
583 1655574334
584 1686009294
585 1716973467
586 1748475676
587 1780525402
588 1813131544
589 1846302684
590 1880047835
591 1914377162
592 1949300480
593 1984826750
594 2020965678
595 2057727986
596 2095123880
597 2133162922
598 2171855736
599 2211213711
600 2251247596
601 2291967553
602 2333384638
603 2375511000
604 2418358248
605 2461937308
606 2506260054
607 2551338978
608 2597186370
609 2643814093
610 2691234546
611 2739461385
612 2788507678
613 2838385569
614 2889108354
615 2940690529
616 2993146112
617 3046488167
618 3100730861
619 3155889317
620 3211978174
621 3269011522
622 3327004441
623 3385973328
624 3445933456
625 3506899780
626 3568888264
627 3631915920
628 3695999634
629 3761155315
630 3827399642
631 3894750706
632 3963226126
633 4032842849
634 4103618812
635 4175573514
636 4248725475
637 4323092452
638 4398693472
639 4475549053
640 4553679210
641 4633102814
642 4713840215
643 4795912838
644 4879341497
645 4964146710
646 5050350122
647 5137974461
648 5227042135
649 5317574438
650 5409593972
651 5503125145
652 5598191823
653 5694816875
654 5793024164
655 5892839402
656 5994287614
657 6097393070
658 6202181491
659 6308680263
660 6416915845
661 6526913502
662 6638700701
663 6752306110
664 6867758059
665 6985084142
666 7104312815
667 7225474418
668 7348598747
669 7473715000
670 7600853680
671 7730047163
672 7861326986
673 7994723732
674 8130269422
675 8267998521
676 8407944867
677 8550140878
678 8694620661
679 8841420353
680 8990575244
681 9142119848
682 9296091003
683 9452526684
684 9611464469
685 9772940847
686 9936994027
687 10103664665
688 10272992753
689 10445017350
690 10619778783
691 10797319504
692 10977681832
693 11160907000
694 11347038118
695 11536120652
696 11728199254
697 11923316957
698 12121519273
699 12322854590
700 12527369900
701 12735111686
702 12946128024
703 13160469141
704 13378184966
705 13599324621
706 13823939424
707 14052082931
708 14283807768
709 14519165685
710 14758210300
711 15000998320
712 15247586231
713 15498028865
714 15752382891
715 16010707979
716 16273063480
717 16539507104
718 16810099897
719 17084905173
720 17363985018
721 17647400755
722 17935216040
723 18227497930
724 18524312777
725 18825725793
726 19131804419
727 19442618635
728 19758238310
729 20078732688
730 20404173237
731 20734634476
732 21070190461
733 21410913420
734 21756878431
735 22108164864
736 22464851188
737 22827014202
738 23194733588
739 23568092203
740 23947172273
741 24332055537
742 24722826509
743 25119573387
744 25522382767
745 25931340541
746 26346535823
747 26768061092
748 27196009227
749 27630471445
750 28071541259
751 28519315988
752 28973893262
753 29435369242
754 29903843529
755 30379419948
756 30862200942
757 31352287437
758 31849784443
759 32354801211
760 32867446885
761 33387828548
762 33916057057
763 34452247075
764 34996512585
765 35548967813
766 36109730189
767 36678920957
768 37256661051
769 37843069969
770 38438270585
771 39042391386
772 39655560960
773 40277905696
774 40909555501
775 41550645291
776 42201309610
777 42861682404
778 43531901620
779 44212110287
780 44902450194
781 45603061345
782 46314089408
783 47035684832
784 47767997880
785 48511178219
786 49265378497
787 50030756445
788 50807470348
789 51595677978
790 52395541064
791 53207227091
792 54030902958
793 54866733548
794 55714889163
795 56575546460
796 57448882570
797 58335072307
798 59234294925
799 60146736084
800 61072580944
801 62012014172
802 62965226771
803 63932414328
804 64913772030
805 65909494483
806 66919781207
807 67944838771
808 68984874528
809 70040094372
810 71110708095
811 72196932579
812 73298985338
813 74417083410
814 75551449480
815 76702313075
816 77869903575
817 79054447904
818 80256180045
819 81475342652
820 82712177405
821 83966925401
822 85239833418
823 86531154487
824 87841143026
825 89170053697
826 90518147352
827 91885691799
828 93272955127
829 94680204112
830 96107712168
831 97555761712
832 99024636799
833 100514619544
834 102025997582
835 103559067355
836 105114126913
837 106691472851
838 108291410680
839 109914253914
840 111560314628
841 113229905271
842 114923345707
843 116640965920
844 118383096754
845 120150068587
846 121942218150
847 123759890615
848 125603433669
849 127473195316
850 129369531467
851 131292806842
852 133243387650
853 135221638388
854 137227931567
855 139262652981
856 141326189029
857 143418924449
858 145541252596
859 147693576568
860 149876301129
861 152089832488
862 154334586288
863 156610987948
864 158919463399
865 161260438473
866 163634349209
867 166041642892
868 168482770313
869 170958181461
870 173468333990
871 176013696590
872 178594742733
873 181211945403
874 183865787924
875 186556766996
876 189285378689
877 192052118799
878 194857495165
879 197702029344
880 200586245523
881 203510667542
882 206475829011
883 209482276208
884 212530558236
885 215621227397
886 218754847340
887 221931993514
888 225153243880
889 228419177289
890 231730383236
891 235087467665
892 238491041881
893 241941714915
894 245440107111
895 248986854219
896 252582595147
897 256227971739
898 259923639112
899 263670267112
900 267468527277
901 271319091271
902 275222646612
903 279179897168
904 283191551174
905 287258318636
906 291380921154
907 295560094963
908 299796583290
909 304091133197
910 308444504258
911 312857473803
912 317330822960
913 321865332337
914 326461799287
915 331121041228
916 335843881325
917 340631143137
918 345483663863
919 350402299851
920 355387912322
921 360441367326
922 365563549121
923 370755358464
924 376017699840
925 381351481582
926 386757629123
927 392237088483
928 397790814804
929 403419764819
930 409124908529
931 414907238024
932 420767753235
933 426707458992
934 432727378850
935 438828557319
936 445012044693
937 451278892088
938 457630172036
939 464066982821
940 470590429035
941 477201618840
942 483901679196
943 490691757538
944 497573011221
945 504546606409
946 511613729011
947 518775586693
948 526033395726
949 533388375599
950 540841767482
951 548394841069
952 556048876587
953 563805158226
954 571664988088
955 579629695611
956 587700621848
957 595879113809
958 604166544423
959 612564313162
960 621073824354
961 629696489579
962 638433746913
963 647287063471
964 656257919087
965 665347800481
966 674558214958
967 683890697434
968 693346798471
969 702928078110
970 712636122725
971 722472547172
972 732438977774
973 742537047444
974 752768415095
975 763134778394
976 773637848246
977 784279340016
978 795060997073
979 805984593949
980 817051919494
981 828264776296
982 839624998771
983 851134451075
984 862795010189
985 874608563255
986 886577028505
987 898702362727
988 910986540696
989 923431546651
990 936039391233
991 948812120531
992 961751802878
993 974860519233
994 988140382961
995 1001593548509
996 1015222181691
997 1029028458599
998 1043014593585
999 1057182844686
1000 1071535488121