0 0
1 4
2 32
3 104
4 250
5 492
6 845
7 1349
8 2021
9 2871
10 3949
11 5267
12 6830
13 8698
14 10878
15 13370
16 16244
17 19502
18 23139
19 27235
20 31787
21 36785
22 42319
23 48381
24 54956
25 62144
26 69932
27 78300
28 87358
29 97088
30 107465
31 118609
32 130497
33 143099
34 156545
35 170807
36 185850
37 201814
38 218666
39 236366
40 255064
41 274722
42 295295
43 316943
44 339623
45 363285
46 388099
47 414017
48 440984
49 469180
50 498552
51 529040
52 560834
53 593876
54 628101
55 663709
56 700637
57 738815
58 778453
59 819483
60 861830
61 905714
62 951062
63 997794
64 1046140
65 1096022
66 1147355
67 1200379
68 1255011
69 1311161
70 1369079
71 1428677
72 1489860
73 1552888
74 1617668
75 1684100
76 1752454
77 1822632
78 1894529
79 1968425
80 2044217
81 2121795
82 2201449
83 2283071
84 2366546
85 2452174
86 2539842
87 2629430
88 2721248
89 2815178
90 2911095
91 3009319
92 3109727
93 3212189
94 3317035
95 3424137
96 3533360
97 3645044
98 3759056
99 3875256
100 3993994
101 4115132
102 4238525
103 4364533
104 4493013
105 4623815
106 4757309
107 4893347
108 5031774
109 5172970
110 5316782
111 5463050
112 5612164
113 5763966
114 5918291
115 6075539
116 6235547
117 6398145
118 6563743
119 6732173
120 6903260
121 7077424
122 7254492
123 7434284
124 7617230
125 7803152
126 7991865
127 8183809
128 8378801
129 8576651
130 8777809
131 8982087
132 9189290
133 9399878
134 9613658
135 9830430
136 10050664
137 10274162
138 10500719
139 10730815
140 10964247
141 11200805
142 11440979
143 11684561
144 11931336
145 12181804
146 12435752
147 12692960
148 12953938
149 13218468
150 13486325
151 13758029
152 14033357
153 14312079
154 14594725
155 14881067
156 15170870
157 15464674
158 15762246
159 16063346
160 16368524
161 16677542
162 16990155
163 17306923
164 17627603
165 17951945
166 18280519
167 18613077
168 18949364
169 19289960
170 19634612
171 19983060
172 20335894
173 20692856
174 21053681
175 21418969
176 21788457
177 22161875
178 22539833
179 22922063
180 23308290
181 23699134
182 24094322
183 24493574
184 24897520
185 25305882
186 25718375
187 26135639
188 26557391
189 26983341
190 27414139
191 27849497
192 28289120
193 28733668
194 29182848
195 29636360
196 30094874
197 30558092
198 31025709
199 31498405
200 31975877
201 32457815
202 32944909
203 33436851
204 33933326
205 34435034
206 34941662
207 35452890
208 35969428
209 36490958
210 37017155
211 37548739
212 38085387
213 38626769
214 39173615
215 39725597
216 40282380
217 40844704
218 41412236
219 41984636
220 42562654
221 43145952
222 43734185
223 44328113
224 44927393
225 45531675
226 46141729
227 46757207
228 47377754
229 48004150
230 48636042
231 49273070
232 49916024
233 50564546
234 51218271
235 51877999
236 52543367
237 53214005
238 53890723
239 54573153
240 55260920
241 55954844
242 56654552
243 57359664
244 58071010
245 58788212
246 59510885
247 60239869
248 60974781
249 61715231
250 62462069
251 63214907
252 63973350
253 64738258
254 65509238
255 66285890
256 67069084
257 67858422
258 68653499
259 69455195
260 70263107
261 71076825
262 71897239
263 72723941
264 73556516
265 74395864
266 75241572
267 76093220
268 76951718
269 77816648
270 78687585
271 79565449
272 80449817
273 81340259
274 82237705
275 83141727
276 84051890
277 84969134
278 85893026
279 86823126
280 87760384
281 88704362
282 89654615
283 90612103
284 91576383
285 92547005
286 93524939
287 94509737
288 95500944
289 96499540
290 97505072
291 98517080
292 99536554
293 100563036
294 101596061
295 102636629
296 103684277
297 104738535
298 105800413
299 106869443
300 107945150
301 109028554
302 110119182
303 111216554
304 112321700
305 113434142
306 114553395
307 115680499
308 116814971
309 117956321
310 119105599
311 120262317
312 121425980
313 122597648
314 123776828
315 124963020
316 126157294
317 127359152
318 128568089
319 129785185
320 131009937
321 132241835
322 133481969
323 134729831
324 135984906
325 137248294
326 138519482
327 139797950
328 141084808
329 142379538
330 143681615
331 144992159
332 146310647
333 147636549
334 148970995
335 150313457
336 151663400
337 153021964
338 154388616
339 155762816
340 157145714
341 158536772
342 159935445
343 161342893
344 162758573
345 164181935
346 165614149
347 167054667
348 168502934
349 169960130
350 171425702
351 172899090
352 174381484
353 175872326
354 177371051
355 178878859
356 180395187
357 181919465
358 183452903
359 184994933
360 186544980
361 188104264
362 189672212
363 191248244
364 192833590
365 194427672
366 196029905
367 197641529
368 199261961
369 200890611
370 202528729
371 204175727
372 205831010
373 207495838
374 209169618
375 210851750
376 212543504
377 214244282
378 215953479
379 217672375
380 219400367
381 221136845
382 222883099
383 224638521
384 226402496
385 228176324
386 229959392
387 231751080
388 233552698
389 235363628
390 237183245
391 239012869
392 240851877
393 242699639
394 244557485
395 246424787
396 248300910
397 250187194
398 252083006
399 253987706
400 255902644
401 257827182
402 259760675
403 261704483
404 263657963
405 265620465
406 267593359
407 269575997
408 271567724
409 273569920
410 275581932
411 277603100
412 279634814
413 281676416
414 283727241
415 285788689
416 287860097
417 289940795
418 292032193
419 294133623
420 296244410
421 298365974
422 300497642
423 302638734
424 304790680
425 306952802
426 309124415
427 311306959
428 313499751
429 315702101
430 317915459
431 320139137
432 322372440
433 324616828
434 326871608
435 329136080
436 331411714
437 333697812
438 335993669
439 338300765
440 340618397
441 342945855
442 345284629
443 347634011
444 349993286
445 352363954
446 354745302
447 357136610
448 359539388
449 361952918
450 364376475
451 366811579
452 369257507
453 371713529
454 374181175
455 376659717
456 379148420
457 381648824
458 384160196
459 386681796
460 389215174
461 391759592
462 394314305
463 396880873
464 399458553
465 402046595
466 404646569
467 407257727
468 409879314
469 412512910
470 415157762
471 417813110
472 420480544
473 423159306
474 425848631
475 428550119
476 431263007
477 433986525
478 436722283
479 439469513
480 442227440
481 444997684
482 447779472
483 450572024
484 453376970
485 456193532
486 459020925
487 461860789
488 464712341
489 467574791
490 470449789
491 473336547
492 476234270
493 479144618
494 482066798
495 485000010
496 487945924
497 490903742
498 493872659
499 496854355
500 499848027
501 502852865
502 505870559
503 508900301
504 511941276
505 514995184
506 518061212
507 521138540
508 524228878
509 527331408
510 530445305
511 533572289
512 536711537
513 539862219
514 543026065
515 546202247
516 549389930
517 552590854
518 555804186
519 559029086
520 562267304
521 565518002
522 568780335
523 572056063
524 575344343
525 578644325
526 581957779
527 585283857
528 588621704
529 591973100
530 595337192
531 598713120
532 602102674
533 605504996
534 608919221
535 612347149
536 615787917
537 619240655
538 622707173
539 626186603
540 629678070
541 633183394
542 636701702
543 640232114
544 643776460
545 647333862
546 650903435
547 654487019
548 658083731
549 661692681
550 665315719
551 668951957
552 672600500
553 676263208
554 679939188
555 683627540
556 687330134
557 691046072
558 694774449
559 698517145
560 702273257
561 706041875
562 709824889
563 713621391
564 717430466
565 721254014
566 725091122
567 728940870
568 732805168
569 736683098
570 740573735
571 744478999
572 748397967
573 752329709
574 756276155
575 760236377
576 764209440
577 768197284
578 772198976
579 776213576
580 780243034
581 784286412
582 788342765
583 792414053
584 796499333
585 800597655
586 804710989
587 808838387
588 812978894
589 817134490
590 821304222
591 825487130
592 829685204
593 833897486
594 838123011
595 842363779
596 846618827
597 850887185
598 855170863
599 859468893
600 863780300
601 868107104
602 872448332
603 876803004
604 881173150
605 885557792
606 889955945
607 894369649
608 898797921
609 903239771
610 907697249
611 912169367
612 916655130
613 921156598
614 925672778
615 930202670
616 934748344
617 939308802
618 943883039
619 948473135
620 953078087
621 957696885
622 962331619
623 966981281
624 971644856
625 976324444
626 981019032
627 985727600
628 990452258
629 995191988
630 999945765
631 1004715709
632 1009500797
633 1014299999
634 1019115445
635 1023946107
636 1028790950
637 1033652114
638 1038528566
639 1043419266
640 1048326364
641 1053248822
642 1058185595
643 1063138843
644 1068107523
645 1073090585
646 1078090199
647 1083105317
648 1088134884
649 1093181080
650 1098242852
651 1103319140
652 1108412134
653 1113520776
654 1118644001
655 1123784009
656 1128939737
657 1134110115
658 1139297353
659 1144500383
660 1149718130
661 1154952814
662 1160203362
663 1165468694
664 1170751040
665 1176049322
666 1181362455
667 1186692679
668 1192038911
669 1197400061
670 1202778379
671 1208172777
672 1213582160
673 1219008788
674 1224451568
675 1229909400
676 1235384554
677 1240875932
678 1246382429
679 1251906325
680 1257446517
681 1263001895
682 1268574749
683 1274163971
684 1279768446
685 1285390474
686 1291028942
687 1296682730
688 1302354148
689 1308042078
690 1313745395
691 1319466419
692 1325204027
693 1330957089
694 1336727935
695 1342515437
696 1348318460
697 1354139344
698 1359976956
699 1365830156
700 1371701294
701 1377589232
702 1383492825
703 1389414433
704 1395352913
705 1401307115
706 1407279409
707 1413268647
708 1419273674
709 1425296870
710 1431337082
711 1437393150
712 1443467464
713 1449558866
714 1455666191
715 1461791839
716 1467934647
717 1474093445
718 1480270643
719 1486465073
720 1492675560
721 1498904524
722 1505150792
723 1511413184
724 1517694130
725 1523992452
726 1530306965
727 1536640109
728 1542990701
729 1549357551
730 1555743109
731 1562146187
732 1568565590
733 1575003778
734 1581459558
735 1587931730
736 1594422764
737 1600931462
738 1607456619
739 1614000715
740 1620562547
741 1627140905
742 1633738279
743 1640353461
744 1646985236
745 1653636104
746 1660304852
747 1666990260
748 1673694838
749 1680417368
750 1687156625
751 1693915129
752 1700691657
753 1707484979
754 1714297625
755 1721128367
756 1727975970
757 1734842974
758 1741728146
759 1748630246
760 1755551824
761 1762491642
762 1769448455
763 1776424823
764 1783419503
765 1790431245
766 1797462619
767 1804512377
768 1811579264
769 1818665860
770 1825770912
771 1832893160
772 1840035194
773 1847195756
774 1854373581
775 1861571269
776 1868787557
777 1876021175
778 1883274733
779 1890546963
780 1897836590
781 1905146234
782 1912474622
783 1919820474
784 1927186420
785 1934571182
786 1941973475
787 1949395939
788 1956837291
789 1964296241
790 1971775439
791 1979273597
792 1986789420
793 1994325568
794 2001880748
795 2009453660
796 2017046974
797 2024659392
798 2032289609
799 2039940305
800 2047610177
801 2055297915
802 2063006209
803 2070733751
804 2078479226
805 2086245334
806 2094030762
807 2101834190
808 2109658328
809 2117501858
810 2125363455
811 2133245839
812 2141147687
813 2149067669
814 2157008515
815 2164968897
816 2172947480
817 2180947004
818 2188966136
819 2197003536
820 2205061954
821 2213140052
822 2221236485
823 2229354013
824 2237491293
825 2245646975
826 2253823829
827 2262020507
828 2270235654
829 2278472050
830 2286728342
831 2295003170
832 2303299324
833 2311615446
834 2319950171
835 2328306299
836 2336682467
837 2345077305
838 2353493623
839 2361930053
840 2370385220
841 2378861944
842 2387358852
843 2395874564
844 2404411910
845 2412969512
846 2421545985
847 2430144169
848 2438762681
849 2447400131
850 2456059369
851 2464739007
852 2473437650
853 2482158158
854 2490899138
855 2499659190
856 2508441184
857 2517243722
858 2526065399
859 2534909095
860 2543773407
861 2552656925
862 2561562539
863 2570488841
864 2579434416
865 2588402164
866 2597390672
867 2606398520
868 2615428618
869 2624479548
870 2633549885
871 2642642549
872 2651756117
873 2660889159
874 2670044605
875 2679221027
876 2688416990
877 2697635434
878 2706874926
879 2716134026
880 2725415684
881 2734718462
882 2744040915
883 2753386003
884 2762752283
885 2772138305
886 2781547039
887 2790977037
888 2800426844
889 2809899440
890 2819393372
891 2828907180
892 2838443854
893 2848001936
894 2857579961
895 2867180929
896 2876803377
897 2886445835
898 2896111313
899 2905798343
900 2915505450
901 2925235654
902 2934987482
903 2944759454
904 2954554600
905 2964371442
906 2974208495
907 2984068799
908 2993950871
909 3003853221
910 3013778899
911 3023726417
912 3033694280
913 3043685548
914 3053698728
915 3063732320
916 3073789394
917 3083868452
918 3093967989
919 3104091085
920 3114236237
921 3124401935
922 3134591269
923 3144802731
924 3155034806
925 3165290594
926 3175568582
927 3185867250
928 3196189708
929 3206534438
930 3216899915
931 3227289259
932 3237700947
933 3248133449
934 3258589895
935 3269068757
936 3279568500
937 3290092264
938 3300638516
939 3311205716
940 3321797014
941 3332410872
942 3343045745
943 3353704793
944 3364386473
945 3375089235
946 3385816249
947 3396565967
948 3407336834
949 3418132030
950 3428950002
951 3439789190
952 3450652784
953 3461539226
954 3472446951
955 3483379159
956 3494334287
957 3505310765
958 3516311803
959 3527335833
960 3538381280
961 3549451364
962 3560544512
963 3571659144
964 3582798490
965 3593960972
966 3605145005
967 3616353829
968 3627585861
969 3638839511
970 3650118029
971 3661419827
972 3672743310
973 3684091738
974 3695463518
975 3706857050
976 3718275604
977 3729717582
978 3741181379
979 3752670275
980 3764182667
981 3775716945
982 3787276399
983 3798859421
984 3810464396
985 3822094624
986 3833748492
987 3845424380
988 3857125598
989 3868850528
990 3880597545
991 3892369969
992 3904166177
993 3915984539
994 3927828385
995 3939696087
996 3951586010
997 3963501494
998 3975440906
999 3987402606
1000 3999389944