0 1
1 2
2 4
3 8
4 13
5 21
6 31
7 45
8 66
9 81
10 97
11 123
12 148
13 182
14 204
15 252
16 291
17 324
18 352
19 415
20 486
21 540
22 651
23 706
24 781
25 864
26 963
27 1003
28 1148
29 1217
30 1371
31 1409
32 1523
33 1673
34 1974
35 2105
36 2191
37 2317
38 2496
39 2652
40 2726
41 2858
42 3219
43 3268
44 3500
45 3605
46 3864
47 3962
48 4237
49 4334
50 4659
51 4767
52 5235
53 5282
54 5545
55 5798
56 6285
57 6452
58 6752
59 7305
60 7433
61 7523
62 8024
63 8679
64 9012
65 9327
66 9703
67 10103
68 10106
69 10152
70 10270
71 10494
72 10600
73 10741
74 11081
75 11346
76 11655
77 12331
78 12425
79 12875
80 13541
81 14461
82 15025
83 15629
84 16012
85 16520
86 16719
87 17803
88 18551
89 19317
90 19988
91 20264
92 21440
93 22502
94 22689
95 23226
96 23981
97 24694
98 25606
99 26523
100 27150
101 27655
102 28907
103 29417
104 29985
105 30673
106 31206
107 31523
108 32360
109 33972
110 35473
111 36373
112 37136
113 38180
114 38905
115 39917
116 40616
117 42249
118 42670
119 43500
120 44757
121 45589
122 46787
123 49022
124 49399
125 51436
126 51765
127 51942
128 53581
129 54773
130 56163
131 57249
132 58098
133 59678
134 60804
135 61150
136 63023
137 64153
138 64657
139 65145
140 67612
141 68709
142 70551
143 71733
144 72152
145 73166
146 73950
147 74278
148 77753
149 79218
150 80789
151 83388
152 84263
153 84794
154 86495
155 88408
156 90421
157 91021
158 92875
159 94256
160 95337
161 97251
162 100153
163 101490
164 103840
165 106054
166 107837
167 109102
168 110986
169 112510
170 113151
171 114951
172 116697
173 121097
174 123073
175 124660
176 126280
177 127332
178 127884
179 128803
180 129237
181 130720
182 135124
183 136985
184 137953
185 141577
186 141726
187 144631
188 148277
189 149042
190 151251
191 154063
192 155221
193 158613
194 161420
195 163673
196 166483
197 167305
198 169148
199 169874
200 173510
201 174237
202 176413
203 176838
204 180204
205 181564
206 183926
207 188606
208 191050
209 194275
210 198162
211 202671
212 204390
213 206793
214 209481
215 211768
216 211961
217 215173
218 220452
219 226585
220 227141
221 228867
222 230991
223 233853
224 236616
225 239496
226 242368
227 243292
228 250161
229 250778
230 253206
231 254501
232 256620
233 258230
234 262151
235 265282
236 267698
237 270065
238 273803
239 276571
240 281388
241 282687
242 288838
243 289778
244 291659
245 295766
246 299812
247 301718
248 309155
249 309615
250 317683
251 319357
252 319651
253 321312
254 324962
255 327779
256 329384
257 333420
258 337518
259 348024
260 348232
261 352767
262 360028
263 363655
264 364682
265 365047
266 370264
267 373372
268 377768
269 379050
270 386214
271 391337
272 394372
273 398923
274 406982
275 410706
276 414684
277 419997
278 421724
279 426471
280 427731
281 429379
282 435588
283 436725
284 448517
285 452432
286 453177
287 463828
288 466564
289 468621
290 472739
291 475020
292 480844
293 483856
294 490440
295 499641
296 502619
297 503072
298 504489
299 508434
300 511604
301 514427
302 516689
303 531207
304 543705
305 544226
306 545684
307 550413
308 550889
309 555604
310 557469
311 565163
312 571965
313 576423
314 582781
315 584323
316 586056
317 587753
318 596315
319 601067
320 604550
321 605787
322 609234
323 618326
324 638112
325 640721
326 649970
327 651281
328 654591
329 667415
330 669645
331 671432
332 684253
333 685528
334 686830
335 690998
336 702815
337 706055
338 711936
339 719360
340 719856
341 723696
342 729409
343 736862
344 747685
345 753746
346 762621
347 764330
348 769448
349 772608
350 785152
351 788157
352 796715
353 801607
354 802394
355 811144
356 816043
357 817925
358 825454
359 829173
360 837700
361 847540
362 868535
363 871040
364 876485
365 879458
366 883360
367 887032
368 888585
369 910714
370 912368
371 919341
372 926902
373 932113
374 936367
375 939886
376 942251
377 947220
378 957201
379 959108
380 960393
381 961321
382 971146
383 985343
384 989846
385 990298
386 1008754
387 1010291
388 1036603
389 1039813
390 1050094
391 1070674
392 1073201
393 1077002
394 1087456
395 1088551
396 1090687
397 1094048
398 1104928
399 1107196
400 1112904
401 1127835
402 1144389
403 1148317
404 1152329
405 1155271
406 1165672
407 1180970
408 1197037
409 1199407
410 1204633
411 1208509
412 1218314
413 1230830
414 1236187
415 1238270
416 1249252
417 1249650
418 1253525
419 1264159
420 1278325
421 1282145
422 1285013
423 1300469
424 1302986
425 1314167
426 1330380
427 1337238
428 1341839
429 1346629
430 1365378
431 1378505
432 1379961
433 1384201
434 1384481
435 1397757
436 1404244
437 1417897
438 1425265
439 1428073
440 1430781
441 1440000
442 1456915
443 1473046
444 1489008
445 1492134
446 1510928
447 1548233
448 1549472
449 1557738
450 1573969
451 1577460
452 1581599
453 1589875
454 1597806
455 1604058
456 1607266
457 1616101
458 1623486
459 1626035
460 1632825
461 1651558
462 1677530
463 1678540
464 1695364
465 1701798
466 1713989
467 1715559
468 1729698
469 1731165
470 1733762
471 1757941
472 1767308
473 1772883
474 1793519
475 1796745
476 1804762
477 1819727
478 1826651
479 1840857
480 1843539
481 1852179
482 1859858
483 1865008
484 1880074
485 1900246
486 1906132
487 1920775
488 1932685
489 1945168
490 1951076
491 1960480
492 1970321
493 1978832
494 2005202
495 2023281
496 2024777
497 2050306
498 2054531
499 2063657
500 2077061
501 2085461
502 2099032
503 2116442
504 2121299
505 2131043
506 2138402
507 2148026
508 2148915
509 2164645
510 2177451
511 2193493
512 2221254
513 2224682
514 2226551
515 2241627
516 2248251
517 2249247
518 2267743
519 2287432
520 2298873
521 2308730
522 2315691
523 2319065
524 2330136
525 2377549
526 2387954
527 2392460
528 2418595
529 2420367
530 2425124
531 2435783
532 2441395
533 2465807
534 2469823
535 2470518
536 2506578
537 2513189
538 2531691
539 2537871
540 2550839
541 2564679
542 2566642
543 2575434
544 2599035
545 2623664
546 2627954
547 2645682
548 2657853
549 2661637
550 2698064
551 2713231
552 2728415
553 2731078
554 2763211
555 2779136
556 2790211
557 2803670
558 2807350
559 2820752
560 2824345
561 2840201
562 2862667
563 2876391
564 2889756
565 2900443
566 2913159
567 2928293
568 2935909
569 2949167
570 2966856
571 2992378
572 2997296
573 3019698
574 3037743
575 3057351
576 3058311
577 3062064
578 3089613
579 3110330
580 3122959
581 3138203
582 3145234
583 3166304
584 3170584
585 3197007
586 3214212
587 3218176
588 3232360
589 3277482
590 3286239
591 3288379
592 3320732
593 3323757
594 3325960
595 3340280
596 3359447
597 3399941
598 3416536
599 3434026
600 3445902
601 3470143
602 3474878
603 3491151
604 3509510
605 3518203
606 3525950
607 3550849
608 3569029
609 3586295
610 3607595
611 3625656
612 3627795
613 3638629
614 3665280
615 3667129
616 3691120
617 3721090
618 3728657
619 3758948
620 3759555
621 3771539
622 3776085
623 3823310
624 3835050
625 3838668
626 3840426
627 3881718
628 3891377
629 3905756
630 3921266
631 3922312
632 3939788
633 3944158
634 4017725
635 4033463
636 4053722
637 4082086
638 4093577
639 4112658
640 4133204
641 4162249
642 4164884
643 4195028
644 4210532
645 4214035
646 4223770
647 4244633
648 4272582
649 4277664
650 4288430
651 4335607
652 4338663
653 4347230
654 4357758
655 4390887
656 4395349
657 4439825
658 4441302
659 4447359
660 4460097
661 4493847
662 4518280
663 4530427
664 4549413
665 4563884
666 4581450
667 4586639
668 4595926
669 4603120
670 4608131
671 4635058
672 4654659
673 4668167
674 4674102
675 4715113
676 4726808
677 4751678
678 4769737
679 4791707
680 4797410
681 4835457
682 4840361
683 4856120
684 4861213
685 4874318
686 4907468
687 4924067
688 4941071
689 4977360
690 4980728
691 5004924
692 5024558
693 5046625
694 5067957
695 5110844
696 5119310
697 5123437
698 5142685
699 5179483
700 5197844
701 5203502
702 5218311
703 5249914
704 5263760
705 5315850
706 5323097
707 5325213
708 5341545
709 5355755
710 5404167
711 5414057
712 5470168
713 5521308
714 5522397
715 5529903
716 5560063
717 5619263
718 5633956
719 5656471
720 5661797
721 5665754
722 5686096
723 5713213
724 5717029
725 5804527
726 5804640
727 5811870
728 5830553
729 5841522
730 5845589
731 5853126
732 5903754
733 5932859
734 5939715
735 5948729
736 5950712
737 6022933
738 6055102
739 6077552
740 6126289
741 6153371
742 6191567
743 6215407
744 6234516
745 6254227
746 6259371
747 6266972
748 6269321
749 6286639
750 6292247
751 6337600
752 6365634
753 6382702
754 6392609
755 6414284
756 6461592
757 6466996
758 6471318
759 6502976
760 6504018
761 6543768
762 6549782
763 6561600
764 6574760
765 6592989
766 6607863
767 6614047
768 6750831
769 6775590
770 6832384
771 6841073
772 6855499
773 6861371
774 6893562
775 6910838
776 6964354
777 6973004
778 7008839
779 7015555
780 7042228
781 7053582
782 7075985
783 7121600
784 7128659
785 7159224
786 7179161
787 7205864
788 7221965
789 7237394
790 7243359
791 7256064
792 7304158
793 7314526
794 7323843
795 7380168
796 7393126
797 7436960
798 7459106
799 7518886
800 7561250
801 7573749
802 7587704
803 7591865
804 7601501
805 7620909
806 7641555
807 7649301
808 7740930
809 7769323
810 7821691
811 7860868
812 7865199
813 7874501
814 7888470
815 7920762
816 7924943
817 7953274
818 8021539
819 8037490
820 8061462
821 8066763
822 8072608
823 8081261
824 8153096
825 8189379
826 8221433
827 8227640
828 8238294
829 8259830
830 8330245
831 8348620
832 8392939
833 8410246
834 8427723
835 8487269
836 8527901
837 8567526
838 8610922
839 8644055
840 8651853
841 8679579
842 8704625
843 8708927
844 8722862
845 8739729
846 8849857
847 8874188
848 8940273