0 1
1 0
2 1
3 1
4 1
5 1
6 2
7 2
8 3
9 3
10 4
11 4
12 6
13 6
14 8
15 9
16 11
17 12
18 15
19 16
20 20
21 22
22 26
23 29
24 35
25 38
26 45
27 50
28 58
29 64
30 75
31 82
32 95
33 105
34 120
35 133
36 152
37 167
38 190
39 210
40 237
41 261
42 295
43 324
44 364
45 401
46 448
47 493
48 551
49 604
50 673
51 739
52 820
53 899
54 997
55 1091
56 1207
57 1321
58 1457
59 1593
60 1756
61 1916
62 2108
63 2301
64 2525
65 2753
66 3019
67 3287
68 3599
69 3917
70 4281
71 4655
72 5084
73 5521
74 6021
75 6537
76 7118
77 7721
78 8401
79 9103
80 9894
81 10715
82 11631
83 12587
84 13653
85 14761
86 15995
87 17285
88 18710
89 20203
90 21854
91 23579
92 25483
93 27480
94 29671
95 31975
96 34502
97 37153
98 40058
99 43114
100 46447
101 49958
102 53787
103 57815
104 62202
105 66826
106 71844
107 77140
108 82885
109 88939
110 95502
111 102428
112 109914
113 117820
114 126362
115 135376
116 145105
117 155382
118 166450
119 178148
120 190741
121 204038
122 218343
123 233460
124 249691
125 266850
126 285266
127 304722
128 325589
129 347644
130 371264
131 396235
132 422966
133 451209
134 481424
135 513361
136 547483
137 583553
138 622077
139 662780
140 706228
141 752141
142 801100
143 852841
144 907990
145 966247
146 1028311
147 1093881
148 1163672
149 1237403
150 1315853
151 1398699
152 1486806
153 1579853
154 1678733
155 1783153
156 1894077
157 2011173
158 2135511
159 2266766
160 2406046
161 2553058
162 2709006
163 2873560
164 3048045
165 3232148
166 3427249
167 3633082
168 3851139
169 4081118
170 4324669
171 4581514
172 4853375
173 5140036
174 5443362
175 5763114
176 6101337
177 6457834
178 6834755
179 7231982
180 7651842
181 8094202
182 8561620
183 9054025
184 9574106
185 10121903
186 10700327
187 11309427
188 11952388
189 12629349
190 13343681
191 14095665
192 14888948
193 15723845
194 16604348
195 17530906
196 18507742
197 19535498
198 20618750
199 21758213
200 22958885
201 24221662
202 25551860
203 26950630
204 28423719
205 29972412
206 31602982
207 33316969
208 35121051
209 37017102
210 39012359
211 41108898
212 43314606
213 45631907
214 48069220
215 50629417
216 53321604
217 56148961
218 59121412
219 62242605
220 65523150
221 68967275
222 72586473
223 76385415
224 80376601
225 84565334
226 88965006
227 93581686
228 98429865
229 103516232
230 108856556
231 114458360
232 120338553
233 126505657
234 132977979
235 139764900
236 146886308
237 154352693
238 162185418
239 170396269
240 179008369
241 188034661
242 197500268
243 207419590
244 217819622
245 228716454
246 240139305
247 252105826
248 264647729
249 277784564
250 291550460
251 305967142
252 321071539
253 336887446
254 353454932
255 370800273
256 388966592
257 407982979
258 427896102
259 448737775
260 470558598
261 493393590
262 517297263
263 542308250
264 568485511
265 595871252
266 624529377
267 654506234
268 685870675
269 718673680
270 752989728
271 788874437
272 826408480
273 865652799
274 906694351
275 949600012
276 994463792
277 1041358575
278 1090386157
279 1141626242
280 1195188567
281 1251160390
282 1309660347
283 1370783432
284 1434658015
285 1501387815
286 1571111238
287 1643941625
288 1720028535
289 1799495225
290 1882503484
291 1969187668
292 2059722206
293 2154253666
294 2252970488
295 2356031920
296 2463641678
297 2575973119
298 2693245885
299 2815648795
300 2943419040
301 3076761571
302 3215932719
303 3361155310
304 3512705655
305 3670826126
306 3835815019
307 4007935192
308 4187508831
309 4374821379
310 4570220122
311 4774015137
312 4986581183
313 5208254261
314 5439438976
315 5680499820
316 5931872788
317 6193953382
318 6467211934
319 6752076658
320 7049055093
321 7358611281
322 7681292054
323 8017600390
324 8368125918
325 8733412814
326 9114097067
327 9510767848
328 9924110168
329 10354761993
330 10803461696
331 11270898969
332 11757869854
333 12265120410
334 12793507817
335 13343839194
336 13917038068
337 14513976386
338 15135649382
339 15782999481
340 16457097999
341 17158963594
342 17889750077
343 18650557170
344 19442627656
345 20267149235
346 21125459279
347 22018840529
348 22948732702
349 23916519695
350 24923751597
351 25971921890
352 27062698046
353 28197691817
354 29378697562
355 30607453045
356 31885889256
357 33215880260
358 34599502573
359 36038777192
360 37535937691
361 39093161706
362 40712851876
363 42397355057
364 44149253967
365 45971077732
366 47865603276
367 49835554142
368 51883916073
369 54013622357
370 56227881398
371 58529852196
372 60922982936
373 63410673488
374 65996629750
375 68684511181
376 71478298479
377 74381930228
378 77399682891
379 80535792980
380 83794854557
381 87181424877
382 90700436850
383 94356792378
384 98155788628
385 102102695456
386 106203201020
387 110462970936
388 114888110517
389 119484710302
390 124259323814
391 129218495292
392 134369258965
393 139718646652
394 145274205606
395 151043490844
396 157034600290
397 163255647614
398 169715321140
399 176422334398
400 183386005756
401 190615692008
402 198121387450
403 205913135741
404 214001655327
405 222397726882
406 231112841741
407 240158570449
408 249547232874
409 259291242891
410 269403807707
411 279898245458
412 290788710246
413 302089488801
414 313815749761
415 325982813934
416 338606935823
417 351704544293
418 365293052662
419 379390076024
420 394014268464
421 409184511313
422 424920786160
423 441243330366
424 458173541866
425 475733109007
426 493944945536
427 512832288395
428 532419672240
429 552731991431
430 573795509954
431 595636894760
432 618284259489
433 641766162604
434 666112694884
435 691354438152
436 717523592049
437 744652901347
438 772776820336
439 801930401337
440 832150507537
441 863474658345
442 895942286014
443 929593546082
444 964470615958
445 1000616462952
446 1038076196366
447 1076895788196
448 1117123473799
449 1158808434285
450 1202002244025
451 1246757506248
452 1293129359846
453 1341174063256
454 1390950555260
455 1442518996585
456 1495942382780
457 1551285034846
458 1608614277608
459 1667998873643
460 1729510761711
461 1793223444250
462 1859213783962
463 1927560335249
464 1998345213273
465 2071652363687
466 2147569498304
467 2226186313808
468 2307596492094
469 2391895857915
470 2479184459437
471 2569564658271
472 2663143284150
473 2760029669114
474 2860337874262
475 2964184657119
476 3071691787001
477 3182983939031
478 3298191091750
479 3417446359828
480 3540888471988
481 3668659530953
482 3800907589550
483 3937784330504
484 4079447733930
485 4226059690415
486 4377788757812
487 4534807695021
488 4697296327316
489 4865438993238
490 5039427511525
491 5219458554855
492 5405736716387
493 5598471797388
494 5797881993910
495 6004191089965
496 6217631756932
497 6438442667454
498 6666871905660
499 6903173987381
500 7147613403419
501 7400461537477
502 7662000334882
503 7932519133963
504 8212318458225
505 8501706746502
506 8801004292327
507 9110539863304
508 9430654779779
509 9761699440614
510 10104037539426
511 10458042480459
512 10824101758016
513 11202613252806
514 11593989766275
515 11998655215416
516 12417049320231
517 12849623680297
518 13296846642925
519 13759199250611
520 14237180281525
521 14731302087397
522 15242095804840
523 15770107065418
524 16315901407288
525 16880059846699
526 17463184481164
527 18065893942819
528 18688829191864
529 19332648832826
530 19998035130254
531 20685689175717
532 21396337116838
533 22130725197489
534 22889626199043
535 23673834333317
536 24484171930222
537 25321484171351
538 26186646014985
539 27080556793543
540 28004147375395
541 28958374604971
542 29944228738305
543 30962727712434
544 32014924845362
545 33101902960474
546 34224782350601
547 35384714734516
548 36582891524898
549 37820537603379
550 39098919883252
551 40419340929737
552 41783147817756
553 43191725573933
554 44646506372182
555 46148962782830
556 47700617296642
557 49303035410472
558 50957835480760
559 52666681620114
560 54431293926600
561 56253441176489
562 58134951420234
563 60077704502214
564 62083643024997
565 64154764670248
566 66293133581018
567 68500872467827
568 70780174400120
569 73133294731244
570 75562563301895
571 78070376155865
572 80659208209348
573 83331604741719
574 86090194522002
575 88937681110430
576 91876856445764
577 94910591929206
578 98041852530804
579 101273687638516
580 104609245675782
581 108051764754817
582 111604587810526
583 115271153027617
584 119055009553627
585 122959807683351
586 126989315143557
587 131147407076135
588 135438082901269
589 139865456068437
590 144433771566310
591 149147395423658
592 154010832859601
593 159028717580151
594 164205830577258
595 169547089188445
596 175057566618323
597 180742480744307
598 186607214355482
599 192657303752696
600 198898459715743
601 205336555864999
602 211977650437019
603 218827974389817
604 225893953983055
605 233182198680700
606 240699524549044
607 248452941922341
608 256449679705652
609 264697172786563
610 273203087241306
611 281975307549573
612 291021962720338
613 300351413275848
614 309972278391526
615 319893422632066
616 330123984105866
617 340673361016604
618 351551240852262
619 362767586716632
620 374332667655984
621 386257044755099
622 398551602605070
623 411227535231907
624 424296378729438
625 437769996986422
626 451660615596571
627 465980807369037
628 480743527522569
629 495962099054767
630 511650249249551
631 527822094870034
632 544492180101768
633 561675461557083
634 579387347665042
635 597643683569077
636 616460791998122
637 635855458024690
638 655844971551113
639 676447111916780
640 697680192015780
641 719563042844131
642 742115059290166
643 765356184589160
644 789306957932749
645 813988498824425
646 839422556529906
647 865631494432433
648 892638341373113
649 920466775976711
650 949141180042816
651 978686622837746
652 1009128916565728
653 1040494600737693
654 1072810999780149
655 1106106207453657
656 1140409146775649
657 1175749554490676
658 1212158043344816
659 1249666086728563
660 1288306083371306
661 1328111342134809
662 1369116149321846
663 1411355753627073
664 1454866436107020
665 1499685495424520
666 1545851320560233
667 1593403376332656
668 1642382279065048
669 1692829782396458
670 1744788855963408
671 1798303671651391
672 1853419685385658
673 1910183623813640
674 1968643569440590
675 2028848947766345
676 2090850615838378
677 2154700850011588
678 2220453438029392
679 2288163667403588
680 2357888421284592
681 2429686167497011
682 2503617058287911
683 2579742920204940
684 2658127357851721
685 2738835744618347
686 2821935330732554
687 2907495234890060
688 2995586556709226
689 3086282369472081
690 3179657837133821
691 3275790208195159
692 3374758937587100
693 3476645681739842
694 3581534425472149
695 3689511478492228
696 3800665607467725
697 3915088033997091
698 4032872572216408
699 4154115628323258
700 4278916343875762
701 4407376597135372
702 4539601152263573
703 4675697662539440
704 4815776825849994
705 4959952389889680
706 5108341314129116
707 5261063777295074
708 5418243346056785
709 5580006984866934
710 5746485231807593
711 5917812210923675
712 6094125815448224
713 6275567722967822
714 6462283586304936
715 6654423051621884
716 6852139957453296
717 7055592355914206
718 7264942720142730
719 7480357968993853
720 7702009683215506
721 7930074133769089
722 8164732507290771
723 8406170938239668
724 8654580743950835
725 8910158461046539
726 9173106090455514
727 9443631138265483
728 9721946871326791
729 10008272362792994
730 10302832758670328
731 10605859328537587
732 10917589743476102
733 11238268132195730
734 11568145371038294
735 11907479145806515
736 12256534254264699
737 12615582674231885
738 12984903879083652
739 13364784912387942
740 13755520717187122
741 14157414217535811
742 14570776662060187
743 14995927713034087
744 15433195804798579
745 15882918240722167
746 16345441567356449
747 16821121679708550
748 17310324211714206
749 17813424650549670
750 18330808744097750
751 18862872624717226
752 19410023234688683
753 19972678459955132
754 20551267574226092
755 21146231383516799
756 21758022689691108
757 22387106446308799
758 23033960242720357
759 23699074471829549
760 24382952835531788
761 25086112525338900
762 25809084750063846
763 26552414929917834
764 27316663247697590
765 28102404857078229
766 28910230458224191
767 29740746521357110
768 30594575887833515
769 31472358009721008
770 32374749577763476
771 33302424777816366
772 34256075946770936
773 35236413847085986
774 36244168351875075
775 37280088738406628
776 38344944403960866
777 39439525179304748
778 40564642076563375
779 41721127624081611
780 42909836647700279
781 44131646628042697
782 45387458517015988
783 46678197118702609
784 48004811942530343
785 49368277609389407
786 50769594743074294
787 52209790402852407
788 53689919015241243
789 55211062834416341
790 56774332915997984
791 58380869607150070
792 60031843564225336
793 61728456274005942
794 63471941117547772
795 65263563924185182
796 67104624083512292
797 68996455134277593
798 70940425926633416
799 72937941247623792
800 74990443036360418
801 77099411048003621
802 79266364124107587
803 81492860897526951
804 83780501120385844
805 86130926411915470
806 88545821647066447
807 91026915749491511
808 93575983143394077
809 96194844594448003
810 98885368727710111
811 101649472918821926
812 104489124881419357
813 107406343611201392
814 110403201045831762
815 113481823065072683
816 116644391226432478
817 119893143824111780
818 123230377704302656
819 126658449385951003
820 130179776959165387
821 133796841271466516
822 137512187913050579
823 141328428471728998
824 145248242609490483
825 149274379389628345
826 153409659448589832
827 157656976399497046
828 162019299103590874
829 166499673153883054
830 171101223251256021
831 175827154772301230
832 180680756254673773
833 185665401053945680
834 190784549943167041
835 196041752863080564
836 201440651641653330
837 206984981842361137
838 212678575608989865
839 218525363617522127
840 224529378051900409
841 230694754664571353
842 237025735889779440
843 243526673018219347
844 250202029453961095
845 257056383009561888
846 264094429313161412
847 271320984229916583
848 278740987426754229
849 286359504926441935
850 294181732837020778
851 302213000045789615
852 310458772120928029
853 318924654152197402
854 327616394833289514
855 336539889456540923
856 345701184184083896
857 355106479204924953
858 364762133203520434
859 374674666687091752
860 384850766661360128
861 395297290136533376
862 406021269019486015
863 417029913807986723
864 428330618709218304
865 439930965531360313
866 451838729039550589
867 464061881054555496
868 476608596056843748
869 489487255503319021
870 502706453690858884
871 516275002301636747
872 530201936538790190
873 544496519911565269
874 559168250655369230
875 574226866769311328
876 589682352733658579
877 605544944811935359
878 621825138080230113
879 638533692006794659
880 655681637807272022
881 673280284316209813
882 691341225683135222
883 709876347550007726
884 728897835104623903
885 748418179578923474
886 768450186675868013
887 789006983405109399
888 810102026900448546
889 831749111609039389
890 853962378518235073
891 876756322715486590
892 900145803043094114
893 924146050047717594
894 948772676082630338
895 974041683665465163
896 999969476049427344
897 1026572866009022495
898 1053869086901459633
899 1081875801902016680
900 1110611115578079111
901 1140093583595584566
902 1170342224830179420
903 1201376531567435642
904 1233216482175454961
905 1265882551823660678
906 1299395725742545851
907 1333777510485695101
908 1369049947804609062
909 1405235626480034809
910 1442357696839739000
911 1480439883187527377
912 1519506498993377244
913 1559582459948492594
914 1600693299859661187
915 1642865184360283677
916 1686124927540870134
917 1730500006348527557
918 1776018577987245842
919 1822709495038395635
920 1870602323667155654
921 1919727359498384186
922 1970115646665719953
923 2021798994479981057
924 2074809997359425511
925 2129182052328055938
926 2184949379868502880
927 2242147042289641436
928 2300810965543897541
929 2360977958506675286
930 2422685735802092362
931 2485972938037091378
932 2550879155682894495
933 2617444950308981307
934 2685711879568071414
935 2755722519478552183
936 2827520490563287121
937 2901150481229662846
938 2976658275116151468
939 3054090775621735925
940 3133496034514889988
941 3214923277667919959
942 3298422934985835569
943 3384046667401947131
944 3471847398188115018
945 3561879341270888357
946 3654198033985608126
947 3748860366776540086
948 3845924617460481643
949 3945450482375427122
950 4047499112223777904
951 4152133144737391211
952 4259416742171773025
953 4369415625560003191
954 4482197113932876269
955 4597830160235578228
956 4716385392353674884
957 4837935150770181264
958 4962553531478921192
959 5090316425464762559
960 5221301563589925666
961 5355588557981922785
962 5493258948983872365
963 5634396248538923255
964 5779085989297649624
965 5927415770093467639
966 6079475307304768646
967 6235356482518003427
968 6395153396248305376
969 6558962417891735654
970 6726882241910626171
971 6899013940182831840
972 7075461020763203808
973 7256329482740372814
974 7441727877692544093
975 7631767367167768916
976 7826561786955259234
977 8026227707312202687
978 8230884500177656672
979 8440654402272180774
980 8655662585388926678
981 8876037222498533095
982 9101909561255643884
983 9333413993249406326
984 9570688130870276947
985 9813872879850355562
986 10063112519643766080
987 10318554779408019683
988 10580350922055577348
989 10848655823836269997
990 11123628062225148613
991 11405429999270604992
992 11694227873493022080
993 11990191887171145053
994 12293496302431167499
995 12604319532653750829
996 12922844242941665125
997 13249257445835350421
998 13583750606357743450
999 13926519742235197038
1000 14277765533724172950