0 1
1 0
2 1
3 1
4 2
5 2
6 4
7 4
8 6
9 7
10 10
11 11
12 16
13 17
14 23
15 26
16 33
17 37
18 47
19 52
20 64
21 72
22 86
23 96
24 115
25 127
26 149
27 166
28 192
29 212
30 245
31 269
32 307
33 338
34 382
35 419
36 472
37 515
38 576
39 629
40 699
41 760
42 843
43 913
44 1007
45 1091
46 1197
47 1293
48 1416
49 1525
50 1663
51 1790
52 1945
53 2088
54 2265
55 2426
56 2623
57 2807
58 3026
59 3232
60 3479
61 3708
62 3981
63 4240
64 4541
65 4828
66 5164
67 5481
68 5850
69 6204
70 6609
71 6998
72 7446
73 7873
74 8362
75 8835
76 9368
77 9885
78 10470
79 11034
80 11670
81 12289
82 12979
83 13652
84 14405
85 15135
86 15949
87 16746
88 17625
89 18487
90 19441
91 20372
92 21399
93 22409
94 23514
95 24602
96 25795
97 26965
98 28245
99 29508
100 30880
101 32235
102 33710
103 35162
104 36739
105 38300
106 39984
107 41653
108 43457
109 45239
110 47162
111 49070
112 51118
113 53151
114 55337
115 57502
116 59825
117 62135
118 64602
119 67057
120 69682
121 72288
122 75071
123 77843
124 80791
125 83729
126 86857
127 89968
128 93276
129 96576
130 100072
131 103561
132 107261
133 110947
134 114851
135 118751
136 122868
137 126982
138 131329
139 135666
140 140244
141 144821
142 149639
143 154458
144 159534
145 164604
146 169939
147 175279
148 180883
149 186494
150 192387
151 198279
152 204462
153 210655
154 217139
155 223635
156 230440
157 237250
158 244378
159 251523
160 258986
161 266468
162 274287
163 282118
164 290296
165 298498
166 307047
167 315623
168 324566
169 333528
170 342868
171 352240
172 361990
173 371775
174 381959
175 392171
176 402792
177 413455
178 424528
179 435646
180 447196
181 458783
182 470814
183 482896
184 495423
185 508005
186 521054
187 534151
188 547727
189 561366
190 575485
191 589671
192 604361
193 619110
194 634376
195 649717
196 665576
197 681514
198 697995
199 714548
200 731657
201 748854
202 766609
203 784457
204 802888
205 821405
206 840519
207 859736
208 879552
209 899476
210 920026
211 940676
212 961967
213 983376
214 1005428
215 1027604
216 1050450
217 1073413
218 1097061
219 1120845
220 1145317
221 1169930
222 1195260
223 1220724
224 1246921
225 1273271
226 1300357
227 1327603
228 1355614
229 1383778
230 1412724
231 1441843
232 1471747
233 1501831
234 1532731
235 1563804
236 1595710
237 1627810
238 1660747
239 1693885
240 1727892
241 1762093
242 1797181
243 1832485
244 1868680
245 1905099
246 1942441
247 1980001
248 2018503
249 2057245
250 2096934
251 2136871
252 2177789
253 2218948
254 2261108
255 2303533
256 2346963
257 2390667
258 2435411
259 2480423
260 2526495
261 2572859
262 2620289
263 2668020
264 2716853
265 2765981
266 2816232
267 2866803
268 2918503
269 2970533
270 3023729
271 3077249
272 3131957
273 3187015
274 3243267
275 3299880
276 3357725
277 3415925
278 3475380
279 3535217
280 3596316
281 3657807
282 3720600
283 3783780
284 3848285
285 3913205
286 3979457
287 4046136
288 4114187
289 4182660
290 4252530
291 4322850
292 4394575
293 4466762
294 4540396
295 4614487
296 4690050
297 4766100
298 4843630
299 4921660
300 5001213
301 5081261
302 5162858
303 5244981
304 5328662
305 5412882
306 5498704
307 5585061
308 5673047
309 5761599
310 5851790
311 5942561
312 6035016
313 6128047
314 6222790
315 6318142
316 6415215
317 6512912
318 6612377
319 6712462
320 6814344
321 6916879
322 7021222
323 7126233
324 7233100
325 7340632
326 7450049
327 7560166
328 7672179
329 7784908
330 7899582
331 8014969
332 8132332
333 8250443
334 8370542
335 8491406
336 8614308
337 8737972
338 8863706
339 8990239
340 9118854
341 9248285
342 9379850
343 9512229
344 9646774
345 9782171
346 9919747
347 10058193
348 10198871
349 10340417
350 10484229
351 10628947
352 10775945
353 10923868
354 11074125
355 11225306
356 11378855
357 11533368
358 11690263
359 11848142
360 12008459
361 12169758
362 12333531
363 12498327
364 12665612
365 12833940
366 13004814
367 13176731
368 13351230
369 13526814
370 13704996
371 13884284
372 14066228
373 14249278
374 14435022
375 14621915
376 14811518
377 15002292
378 15195836
379 15390551
380 15588075
381 15786814
382 15988379
383 16191182
384 16396872
385 16603801
386 16813656
387 17024796
388 17238880
389 17454272
390 17672671
391 17892379
392 18115135
393 18339246
394 18566424
395 18794982
396 19026670
397 19259740
398 19495982
399 19733654
400 19974517
401 20216835
402 20462410
403 20709442
404 20959774
405 21211612
406 21466770
407 21723460
408 21983537
409 22245149
410 22510192
411 22776820
412 23046900
413 23318592
414 23593804
415 23870632
416 24151025
417 24433085
418 24718732
419 25006074
420 25297073
421 25589770
422 25886171
423 26184323
424 26486201
425 26789859
426 27097314
427 27406554
428 27719638
429 28034561
430 28353352
431 28674011
432 28998611
433 29325084
434 29655547
435 29987938
436 30324343
437 30662707
438 31005159
439 31349576
440 31698131
441 32048707
442 32403446
443 32760238
444 33121269
445 33484359
446 33851739
447 34221236
448 34595049
449 34971011
450 35351367
451 35733879
452 36120837
453 36510010
454 36903656
455 37299551
456 37699997
457 38102700
458 38510008
459 38919633
460 39333891
461 39750500
462 40171823
463 40595505
464 41023956
465 41454828
466 41890497
467 42328623
468 42771628
469 43217099
470 43667505
471 44120440
472 44578340
473 45038805
474 45504319
475 45972408
476 46445603
477 46921437
478 47402408
479 47886056
480 48374926
481 48866483
482 49363321
483 49862912
484 50367815
485 50875510
486 51388604
487 51904501
488 52425857
489 52950083
490 53479801
491 54012428
492 54550636
493 55091765
494 55638536
495 56188297
496 56743733
497 57302200
498 57866432
499 58433708
500 59006812
501 59583029
502 60165109
503 60750344
504 61341534
505 61935892
506 62536269
507 63139886
508 63749557
509 64362511
510 64981613
511 65604012
512 66232624
513 66864606
514 67502838
515 68144484
516 68792475
517 69443895
518 70101727
519 70763062
520 71430847
521 72102180
522 72780060
523 73461504
524 74149563
525 74841262
526 75539614
527 76241653
528 76950444
529 77662938
530 78382254
531 79105350
532 79835308
533 80569093
534 81309841
535 82054434
536 82806060
537 83561610
538 84324234
539 85090831
540 85864604
541 86642368
542 87427381
543 88216465
544 89012840
545 89813336
546 90621227
547 91433258
548 92252758
549 93076480
550 93907714
551 94743221
552 95586346
553 96433764
554 97288875
555 98148363
556 99015588
557 99887242
558 100766741
559 101650690
560 102542561
561 103438966
562 104343339
563 105252300
564 106169338
565 107090986
566 108020789
567 108955289
568 109897990
569 110845443
570 111801209
571 112761749
572 113730682
573 114704477
574 115686713
575 116673867
576 117669575
577 118670225
578 119679510
579 120693827
580 121716828
581 122744918
582 123781807
583 124823810
584 125874695
585 126930785
586 127995807
587 129066093
588 130145428
589 131230052
590 132323810
591 133422950
592 134531275
593 135645042
594 136768113
595 137896653
596 139034582
597 140178075
598 141331010
599 142489570
600 143657693
601 144831468
602 146014894
603 147204068
604 148402947
605 149607637
606 150822154
607 152042511
608 153272784
609 154508995
610 155755177
611 157007361
612 158269641
613 159537952
614 160816450
615 162101079
616 163395951
617 164697019
618 166008457
619 167326122
620 168654249
621 169988704
622 171333679
623 172685049
624 174047067
625 175415512
626 176794699
627 178180416
628 179576934
629 180980050
630 182394098
631 183814776
632 185246482
633 186684923
634 188134452
635 189590786
636 191058340
637 192532733
638 194018443
639 195511099
640 197015134
641 198526185
642 200048750
643 201578366
644 203119595
645 204667983
646 206228047
647 207795343
648 209374451
649 210960827
650 212559116
651 214164783
652 215782427
653 217407523
654 219044735
655 220689436
656 222346355
657 224010875
658 225687679
659 227372159
660 229069064
661 230773683
662 232490831
663 234215807
664 235953379
665 237698856
666 239457071
667 241223231
668 243002235
669 244789299
670 246589276
671 248397391
672 250218564
673 252047915
674 253890432
675 255741245
676 257605293
677 259477717
678 261363523
679 263257747
680 265165462
681 267081714
682 269011529
683 270949962
684 272902107
685 274862913
686 276837542
687 278820953
688 280818260
689 282824432
690 284844651
691 286873779
692 288917067
693 290969387
694 293035941
695 295111612
696 297201670
697 299300890
698 301414612
699 303537621
700 305675208
701 307822167
702 309983860
703 312154972
704 314340934
705 316536442
706 318746877
707 320966946
708 323202099
709 325446934
710 327706972
711 329976820
712 332261950
713 334556979
714 336867450
715 339187869
716 341523850
717 343869910
718 346231612
719 348603484
720 350991160
721 353389056
722 355802878
723 358227053
724 360667236
725 363117864
726 365584664
727 368061961
728 370555554
729 373059778
730 375580382
731 378111711
732 380659586
733 383218239
734 385793564
735 388379804
736 390982800
737 393596807
738 396227739
739 398869736
740 401528786
741 404199039
742 406886432
743 409585125
744 412301129
745 415028489
746 417773289
747 420529586
748 423303411
749 426088832
750 428891954
751 431706729
752 434539337
753 437383740
754 440246066
755 443120288
756 446012608
757 448916882
758 451839388
759 454773993
760 457726921
761 460692050
762 463675680
763 466671571
764 469686098
765 472713033
766 475758697
767 478816873
768 481893958
769 484983616
770 488092321
771 491213747
772 494354315
773 497507710
774 500680429
775 503866038
776 507071110
777 510289223
778 513526895
779 516777716
780 520048281
781 523332058
782 526635721
783 529952749
784 533289761
785 536640247
786 540010904
787 543395101
788 546799612
789 550217818
790 553656438
791 557108864
792 560581893
793 564068795
794 567576446
795 571098127
796 574640658
797 578197332
798 581775048
799 585366975
800 588980092
801 592607579
802 596256359
803 599919624
804 603604376
805 607303683
806 611024626
807 614760286
808 618517687
809 622289921
810 626084093
811 629893169
812 633724335
813 637570568
814 641438998
815 645322614
816 649228625
817 653149895
818 657093714
819 661052958
820 665034859
821 669032305
822 673052610
823 677088534
824 681147473
825 685222199
826 689320050
827 693433810
828 697570899
829 701723973
830 705900534
831 710093250
832 714309565
833 718542159
834 722798558
835 727071314
836 731368035
837 735681285
838 740018614
839 744372598
840 748750870
841 753145875
842 757565331
843 762001695
844 766462625
845 770940591
846 775443334
847 779963194
848 784507995
849 789070090
850 793657244
851 798261821
852 802891671
853 807539026
854 812211821
855 816902300
856 821618338
857 826352192
858 831111821
859 835889350
860 840692823
861 845514377
862 850361996
863 855227830
864 860119948
865 865030366
866 869967239
867 874922596
868 879904531
869 884905085
870 889932439
871 894978499
872 900051532
873 905143457
874 910262480
875 915400533
876 920565907
877 925750400
878 930962390
879 936193687
880 941452608
881 946730975
882 952037193
883 957362947
884 962716730
885 968090240
886 973491907
887 978913443
888 984363365
889 989833248
890 995331697
891 1000850300
892 1006397600
893 1011965197
894 1017561723
895 1023178640
896 1028824668
897 1034491282
898 1040187140
899 1045903730
900 1051649798
901 1057416693
902 1063213251
903 1069030834
904 1074878214
905 1080746767
906 1086645354
907 1092565211
908 1098515289
909 1104486837
910 1110488743
911 1116512268
912 1122566391
913 1128642232
914 1134748860
915 1140877409
916 1147036883
917 1153218430
918 1159431144
919 1165666032
920 1171932279
921 1178220904
922 1184541029
923 1190883686
924 1197258088
925 1203655124
926 1210084099
927 1216535916
928 1223019814
929 1229526710
930 1236065935
931 1242628262
932 1249223114
933 1255841278
934 1262492112
935 1269166416
936 1275873640
937 1282604440
938 1289368359
939 1296156066
940 1302977039
941 1309821960
942 1316700400
943 1323602896
944 1330539112
945 1337499599
946 1344493954
947 1351512743
948 1358565656
949 1365643112
950 1372754896
951 1379891440
952 1387062463
953 1394258410
954 1401489095
955 1408744816
956 1416035480
957 1423351400
958 1430702416
959 1438078855
960 1445490651
961 1452927983
962 1460400881
963 1467899537
964 1475433914
965 1482994218
966 1490590507
967 1498212838
968 1505871365
969 1513556159
970 1521277306
971 1529024891
972 1536809096
973 1544619856
974 1552467449
975 1560341825
976 1568253193
977 1576191517
978 1584167103
979 1592169764
980 1600209903
981 1608277346
982 1616382429
983 1624514992
984 1632685467
985 1640883543
986 1649119749
987 1657383789
988 1665686122
989 1674016467
990 1682385381
991 1690782429
992 1699218267
993 1707682474
994 1716185637
995 1724717349
996 1733288295
997 1741887915
998 1750526992
999 1759194981
1000 1767902595