0 1
1 2
2 4
3 7
4 11
5 16
6 24
7 31
8 40
9 52
10 68
11 79
12 102
13 115
14 140
15 175
16 201
17 218
18 265
19 284
20 336
21 396
22 446
23 469
24 547
25 599
26 662
27 742
28 837
29 866
30 1034
31 1065
32 1153
33 1275
34 1370
35 1511
36 1719
37 1756
38 1869
39 2030
40 2244
41 2285
42 2613
43 2656
44 2865
45 3236
46 3394
47 3441
48 3780
49 3921
50 4232
51 4489
52 4779
53 4832
54 5294
55 5587
56 6014
57 6325
58 6559
59 6618
60 7507
61 7568
62 7823
63 8568
64 8964
65 9353
66 10161
67 10228
68 10719
69 11154
70 12129
71 12200
72 13270
73 13343
74 13688
75 14760
76 15384
77 15901
78 17054
79 17133
80 18233
81 19227
82 19648
83 19731
84 21696
85 22314
86 22770
87 23428
88 24560
89 24649
90 27427
91 28117
92 29074
93 29818
94 30354
95 31104
96 32885
97 32982
98 34141
99 36148
100 38124
101 38225
102 40260
103 40363
104 41986
105 45566
106 46235
107 46342
108 49488
109 49597
110 52170
111 53199
112 55699
113 55812
114 58451
115 59505
116 61080
117 64048
118 64854
119 65933
120 71902
121 72439
122 73296
123 74541
124 76380
125 77879
126 84263
127 84390
128 86645
129 88001
130 91705
131 91836
132 97500
133 98813
134 99828
135 106737
136 109985
137 110122
138 114262
139 114401
140 121749
141 123353
142 124487
143 125904
144 133005
145 134603
146 135795
147 140538
148 143360
149 143509
150 153300
151 153451
152 157646
153 163370
154 168706
155 170509
156 179246
157 179403
158 180778
159 182784
160 189953
161 191790
162 200098
163 200261
164 203864
165 214523
166 216039
167 216206
168 230675
169 231552
170 238336
171 245821
172 250015
173 250188
174 257305
175 265170
176 273216
177 275685
178 277412
179 277591
180 301969
181 302150
182 309965
183 312584
184 319653
185 322152
186 330696
187 332936
188 338017
189 355390
190 364407
191 364598
192 376683
193 376876
194 378887
195 395128
196 405624
197 405821
198 426266
199 426465
200 442358
201 445496
202 447676
203 450463
204 467542
205 470558
206 472822
207 484973
208 497379
209 500094
210 540671
211 540882
212 547981
213 551487
214 553918
215 557219
216 582679
217 585846
218 588361
219 592050
220 615686
221 618682
222 631763
223 631986
224 650806
225 684908
226 687624
227 687851
228 711187
229 711416
230 725741
231 750773
232 764019
233 764252
234 796398
235 800292
236 809545
237 813849
238 828292
239 828531
240 878534
241 878775
242 886183
243 909035
244 919127
245 936768
246 953862
247 957522
248 973472
249 978189
250 995804
251 996055
252 1060114
253 1063907
254 1067275
255 1100568
256 1118084
257 1118341
258 1137940
259 1142331
260 1179974
261 1202695
262 1206285
263 1206548
264 1256389
265 1261274
266 1280279
267 1285683
268 1298463
269 1298732
270 1378851
271 1379122
272 1406378
273 1445040
274 1448936
275 1471377
276 1511096
277 1511373
278 1515363
279 1542294
280 1615231
281 1615512
282 1640028
283 1640311
284 1655438
285 1700987
286 1722241
287 1727556
288 1786977
289 1788939
290 1814749
291 1821138
292 1837421
293 1837714
294 1898814
295 1904808
296 1931611
297 1992700
298 1997277
299 2002406
300 2106225
301 2112012
302 2116707
303 2123615
304 2161399
305 2167782
306 2234897
307 2235204
308 2297810
309 2304975
310 2335484
311 2335795
312 2416374
313 2416687
314 2421730
315 2564536
316 2584907
317 2585224
318 2618728
319 2624473
320 2688397
321 2696116
322 2726868
323 2732561
324 2819681
325 2853706
326 2859157
327 2867153
328 2903919
329 2910757
330 3058420
331 3058751
332 3081571
333 3125490
334 3131184
335 3138816
336 3276840
337 3277177
338 3292266
339 3300826
340 3379623
341 3386175
342 3479836
343 3490789
344 3533520
345 3610764
346 3616891
347 3617238
348 3691334
349 3691683
350 3803922
351 3902820
352 3979100
353 3979453
354 4023623
355 4032154
356 4059814
357 4139453
358 4145981
359 4146340
360 4412385
361 4415098
362 4421726
363 4461113
364 4563379
365 4572373
366 4621409
367 4621776
368 4690719
369 4748738
370 4797419
371 4805994
372 4898883
373 4899256
374 4938742
375 5049914
376 5106389
377 5114090
378 5343586
379 5343965
380 5456675
381 5467453
382 5474859
383 5475242
384 5581663
385 5701371
386 5708920
387 5774831
388 5810013
389 5810402
390 6053400
391 6061436
392 6179746
393 6191172
394 6199015
395 6209502
396 6455881
397 6456278
398 6464247
399 6571615
400 6732148
401 6732549
402 6795445
403 6804267
404 6843432
405 7100477
406 7156283
407 7165328
408 7348069
409 7348478
410 7412408
411 7424894
412 7466351
413 7476833
414 7641869
415 7653361
416 7779847
417 7792682
418 7845389
419 7845808
420 8381946
421 8382367
422 8391319
423 8476071
424 8559346
425 8624921
426 8698720
427 8709945
428 8755843
429 8874935
430 8948385
431 8948816
432 9215546
433 9215979
434 9282398
435 9432981
436 9481683
437 9491449
438 9571397
439 9571836
440 9863844
441 10116457
442 10175215
443 10175658
444 10335489
445 10348643
446 10358628
447 10373339
448 10573759
449 10574208
450 11063753
451 11074646
452 11128386
453 11143467
454 11153780
455 11346293
456 11604668
457 11605125
458 11615612
459 11842411
460 12044371
461 12044832
462 12469255
463 12469718
464 12614249
465 12801152
466 12812022
467 12812489
468 13229971
469 13243371
470 13336865
471 13353161
472 13470216
473 13482137
474 13581306
475 13667786
476 13895315
477 14014360
478 14025801
479 14026280
480 14565008
481 14577189
482 14588773
483 14776441
484 14899346
485 14914905
486 15201970
487 15202457
488 15332021
489 15349535
490 15671383
491 15671874
492 15890295
493 15902437
494 15979996
495 16593353
496 16774719
497 16789681
498 16903050
499 16903549
500 17156108
501 17174495
502 17187066
503 17187569
504 17990786
505 18007598
506 18094336
507 18182409
508 18256540
509 18257049
510 18807503
511 18823306
512 19002730
513 19328096
514 19341238
515 19358700
516 19619808
517 19633814
518 19739854
519 19759547
520 20260485
521 20261006
522 20599130
523 20599653
524 20680216
525 21371799
526 21385566
527 21399502
528 21984580
529 21989410
530 22118823
531 22279492
532 22604365
533 22618976
534 22755963
535 22774771
536 22950634
537 22971692
538 22986080
539 23108073
540 24263905
541 24264446
542 24279026
543 24300531
544 24609544
545 24629019
546 25337066
547 25337613
548 25428989
549 25606109
550 26021970
551 26036824
552 26512035
553 26530404
554 26545631
555 26861010
556 26956834
557 26957391
558 27382581
559 27398608
560 28328182
561 28582009
562 28597718
563 28598281
564 28936209
565 28957104
566 28972976
567 29776247
568 29994536
569 29995105
570 30794237
571 30794808
572 31181493
573 31205420
574 31346914
575 31489369
576 32126989
577 32127566
578 32176890
579 32201280
580 32612549
581 32632709
582 32805265
583 32822820
584 33055346
585 34128301
586 34145328
587 34145915
588 35042706
589 35059773
590 35234279
591 35259712
592 35592803
593 35593396
594 36568042
595 36986846
596 37103807
597 37129740
598 37257693
599 37258292
600 38639147
601 38639748
602 38801010
603 39031992
604 39153300
605 39324922
606 39519475
607 39520082
608 39973284
609 40343312
610 40535851
611 40554766
612 41508558
613 41509171
614 41527759
615 41956378
616 42942913
617 42943530
618 43150912
619 43151531
620 43665443
621 44270615
622 44289718
623 44312783
624 45319689
625 45453333
626 45472672
627 45814114
628 45949577
629 45968629
630 48686923
631 48687554
632 49002452
633 49031554
634 49051348
635 49077591
636 49580747
637 49767802
638 49923386
639 50195581
640 50967321
641 50967962
642 51197785
643 51198428
644 51784496
645 52286479
646 52433278
647 52433925
648 53576073
649 53597466
650 54286280
651 54746397
652 54897923
653 54898576
654 55142056
655 55169904
656 55640152
657 55935197
658 56143021
659 56143680
660 58532290
661 58532951
662 58554492
663 58940132
664 59301145
665 59890828
666 60640949
667 60661637
668 60824098
669 60856542
670 61109042
671 61132092
672 62875920
673 62876593
674 62898918
675 64878795
676 65208438
677 65209115
678 65480710
679 65508025
680 66743028
681 66776637
682 66965934
683 66966617
684 68364772
685 68395190
686 68638742
687 68672907
688 69235909
689 69259475
690 70726306
691 70726997
692 70905025
693 72892099
694 72915780
695 72947067
696 73955969
697 73978905
698 74002816
699 74038181
700 76009785
701 76010486
702 77704736
703 77728187
704 78725748
705 79393389
706 79417902
707 79447439
708 80156466
709 80157175
710 80455105
711 80824202
712 81285202
713 81309015
714 82957161
715 83634883
716 83832891
717 83870104
718 83895441
719 83896160
720 87568425
721 87599075
722 87682942
723 87720737
724 87923184
725 88185605
726 89021969
727 89022696
728 90775404
729 91788857
730 92112992
731 92138256
732 92943877
733 92944610
734 92970990
735 95112941
736 96020599
737 96047989
738 97099315
739 97100054
740 98038801
741 98564039
742 98858292
743 98859035
744 100144646
745 100180506
746 100207790
747 100633059
748 101497460
749 101530429
750 103529108
751 103529859
752 104309032
753 104349961
754 104578221
755 104615011
756 108435583
757 108436340
758 108464469
759 109049652
760 110875239
761 110876000
762 111250401
763 111284612
764 111520600
765 114264495
766 114293266
767 114322129
768 115625141
769 115625910
770 118589282
771 118632203
772 118876496
773 118877269
774 120124434
775 120438572
776 121061108
777 121857675
778 121887302
779 121915312
780 126188143
781 126218711
782 126462410
783 127784922
784 129585227
785 129624989
786 130034539
787 130035326
788 130294908
789 130339793
790 130746109
791 130782755
792 134494496
793 134525599
794 134556433
795 135529849
796 135796765
797 135797562
798 138182029
799 138211677
800 140398907
801 140922024
802 140953492
803 140985830
804 142079104
805 143142269
806 143421283
807 143468266
808 144177310
809 144178119
810 148768355
811 148769166
812 150004662
813 150052275
814 150355482
815 150398255
816 152919698
817 152950576
818 152983275
819 156532597
820 157850009
821 157850830
822 158314247
823 158315070
824 159078748
825 162156102
826 162555312
827 162556139
828 165195097
829 165195926
830 165666366
831 165716122
832 167498709
833 167855665
834 168341002
835 168385802
836 169646659
837 171307567
838 171341920
839 171342759
840 180531918
841 180541573
842 180576175
843 180627325
844 180942133
845 181367417
846 183038241
847 183468247
848 184693821
849 184745692
850 186284578
851 186317378
852 187665371
853 187666224
854 188107369
855 192223811
856 193105864
857 193106721
858 196013252
859 196014111
860 197604368
861 198712535
862 198748846
863 198749709
864 202374984
865 202422989
866 202459539
867 202814916
868 204390877
869 204428453
870 207644391
871 207681416
872 208614777
873 209285966
874 209609485
875 211425811
876 212922335
877 212923212
878 212960790
879 213016336
880 217780735
881 217781616
882 222928159
883 222929042
884 224388993
885 225774236
886 225812551
887 225813438
888 228239435
889 228285501
890 228858353
891 232561179
892 232932634
893 232968928
894 233558415
895 233609760
896 236613452
897 237516613
898 237555961
899 237591819
900 246413132
901 246450157
902 246854521
903 248126885
904 249195051
905 249247535
906 249864660
907 249865567
908 250253664
909 251006800
910 256271050
911 256271961
912 260084060
913 260125232
914 260165914
915 261707302
916 262108015
917 262156911
918 266354432
919 266355351
920 270011869
921 270072847
922 270114262
923 270155523
924 278666997
925 279174836
926 279216623
927 280011822
928 282090666
929 282091595
930 286250357
931 286730079
932 287153211
933 287215750
934 287258193
935 288755165
936 295428533
937 295429470
938 296006161
939 296069483
940 298177039
941 298177980
942 298868517
943 298907692
944 300699347
945 312027706
946 312499653
947 312500600
948 314478386
949 314522116
950 316708178
951 316773126
952 321485427
953 321486380
954 324006922
955 324065312
956 324517258
957 325703332
958 325748010
959 325801427
960 333476616
961 333488388
962 333937219
963 334827649
964 335290925
965 335350494
966 339934608
967 339935575
968 342487326
969 343578658
970 344317034
971 344318005
972 349002454
973 349057366
974 349103485
975 354587854
976 356653951
977 356654928
978 357423268
979 357470255
980 364241912
981 365182967
982 365229888
983 365230871
984 368738726
985 368800720
986 369233167
987 370948450
988 373057449
989 373100697
990 387097317
991 387098308
992 389793691
993 389864458
994 390552761
995 390616032
996 392913840
997 392914837
998 392963196
999 396046320
1000 400644605
1001 402800033
1002 403621471
1003 403666699
1004 404186975
1005 406280619
1006 406329852
1007 406375295
1008 419378641
1009 419379650
1010 420216306
1011 420289626
1012 422679694
1013 422680707
1014 425008594
1015 427256156
1016 428845766
1017 429892486
1018 429942871
1019 429943890
1020 440795805
1021 440796826
1022 441546678
1023 443007459
1024 445527428
1025 446192375
1026 452514256
1027 452565009
1028 453125008
1029 455478204
1030 456370057
1031 456371088
1032 460569515
1033 460570548
1034 461172779
1035 469435788
1036 472314945
1037 472363813
1038 473281165
1039 473282204
1040 482172822
1041 482250523
1042 482303263
1043 482366106
1044 488162890
1045 490251153
1046 490304325
1047 490382905
1048 492152411
1049 492153460
1050 508802996
1051 508804047
1052 509402482
1053 516070422
1054 516597118
1055 516668150
1056 525901103
1057 525965683
1058 526176860
1059 526257211
1060 529476333
1061 529477394
1062 533080734
1063 533081797
1064 540092430
1065 542639190
1066 543234324
1067 543290095
1068 546225319
1069 546226388
1070 547219424
1071 556503308
1072 559450262
1073 559499625
1074 560508167
1075 561272790
1076 561910452
1077 561993535
1078 565839657
1079 565895217
1080 586862021
1081 586912884
1082 586969686
1083 587603540
1084 588253714
1085 591045650
1086 592093298
1087 592094385
1088 596917085
1089 601589320
1090 602650826
1091 602651917
1092 618262141
1093 618263234
1094 618321238
1095 621093148
1096 623196460
1097 623197557
1098 627346969
1099 627416787
1100 637130830
1101 637217643
1102 637793995
1103 637795098
1104 645348791
1105 647807421
1106 648758082
1107 653217189
1108 653912800
1109 653913909
1110 661599542
1111 661659840
1112 663874723
1113 666409120
1114 666469287
1115 666548498
1116 674039965
1117 674041082
1118 674729333
1119 674818931
1120 691020889
1121 691076141
1122 698029005
1123 698030128
1124 698754911
1125 711658092
1126 711719550
1127 712488173
1128 718327644
1129 718328773
1130 719508586
1131 721306244
1132 722047753
1133 722110306
1134 739063754
1135 739145743
1136 742925045
1137 743017588
1138 743080322
1139 743138446
1140 759624088
1141 759699095
1142 759762243
1143 761229004
1144 770292107
1145 770375518
1146 771597086
1147 771653939
1148 775755276
1149 775849709
1150 779852724
1151 779853875
1152 788978711
1153 788979864
1154 789044271
1155 810100173
1156 811801134
1157 811864626
1158 813132207
1159 813192030
1160 821703798
1161 826959935
1162 828075113
1163 828076276
1164 832083911
1165 832170223
1166 833030223
1167 833127607
1168 837219661
1169 837298260
1170 863562786
1171 863563957
1172 864381532
1173 866237117
1174 866303834
1175 867276146
1176 884101179
1177 884168591
1178 884867370
1179 886475405
1180 891215710
1181 891216891
1182 892556256
1183 893649831
1184 899009685
1185 902623428
1186 902691593
1187 902692780
1188 922459535
1189 922518569
1190 935863509
1191 935964945
1192 938818438
1193 938819631
1194 940203560
1195 940294298
1196 944284353
1197 958222545
1198 958292077
1199 958362111
1200 981968756
1201 981969957
1202 982039835
1203 982143264
1204 987079648
1205 987171877
1206 992877974
1207 992942717
1208 995929613
1209 998160272
1210 1003999675
1211 1004084028
1212 1008687596
1213 1008688809
1214 1008760085
1215 1028554640
1216 1036107884
1217 1036109101
1218 1046336810
1219 1046400456
1220 1051782092
1221 1054335542
1222 1055228219
1223 1055229442
1224 1072708401
1225 1081201802
1226 1081274581
1227 1081382220
1228 1082318072
1229 1082319301
1230 1093358513
1231 1093359744
1232 1114055327
1233 1115893187
1234 1115966825
1235 1119394158
1236 1124398251
1237 1124399488
1238 1124473528
1239 1128112698
1240 1139153267
1241 1139221938
1242 1151779664
1243 1151854589
1244 1152828743
1245 1157123250
1246 1158484062
1247 1158549485
1248 1175532271
1249 1175533520
1250 1178847738
1251 1180757015
1252 1181752257
1253 1181842279
1254 1191985316
1255 1192085239
1256 1195496696
1257 1195609575
1258 1196453552
1259 1196454811
1260 1261312466
1261 1261387698
1262 1261464669
1263 1261578586
1264 1267292100
1265 1271125055
1266 1272771669
1267 1272863882
1268 1273890705
1269 1281155466
1270 1282831882
1271 1282899979
1272 1292119159
1273 1292190357
1274 1298699368
1275 1312840443
1276 1317917979
1277 1317919256
1278 1324968104
1279 1324969383
1280 1338050803
1281 1342164347
1282 1342243871
1283 1342245154
1284 1347954644
1285 1348059330
1286 1348139209
1287 1365210330
1288 1379556638
1289 1379557927
1290 1393123370
1291 1393124661
1292 1398031766
1293 1398151159
1294 1398232045
1295 1403342001
1296 1422888231
1297 1422889528
1298 1424048102
1299 1424168538
1300 1442018353
1301 1442019654
1302 1455493868
1303 1455495171
1304 1459423883
1305 1479874177
1306 1479956580
1307 1479957887
1308 1486138240
1309 1490900789
1310 1492747739
1311 1495263229
1312 1503282564
1313 1503364044
1314 1511191998
1315 1511301609
1316 1518160061
1317 1518283894
1318 1518367862
1319 1518369181
1320 1568317768
1321 1568319089
1322 1568403404
1323 1594112398
1324 1595283951
1325 1596637983
1326 1608560662
1327 1608561989
1328 1615450999
1329 1615577021
1330 1636054309
1331 1636211912
1332 1650793612
1333 1650869113
1334 1651813557
1335 1657293273
1336 1661623732
1337 1661726195
1338 1663657154
1339 1663741794
1340 1671437502
1341 1673782119
1342 1675087902
1343 1675167444
1344 1705827556
1345 1705942168
1346 1706029679
1347 1706159135
1348 1707387799
1349 1707467175
1350 1753258150
1351 1753362745
1352 1762019698
1353 1765575728
1354 1765664265
1355 1765780524
1356 1772808001
1357 1772885573
1358 1774639254
1359 1777070780
1360 1802139697
1361 1802141058
1362 1804158885
1363 1804235686
1364 1810727131
1365 1850554541
1366 1850644746
1367 1850646113
1368 1877463749
1369 1877483841
1370 1879611684
1371 1879745798
1372 1887702128
1373 1887703501
1374 1889788177
1375 1897136517
1376 1906900916
1377 1924688048
1378 1925961496
1379 1926070312
1380 1959538311
1381 1959539692
1382 1959631854
1383 1959768241
1384 1964642963
1385 1964764401
1386 2021070438
1387 2021154766
1388 2022496829
1389 2022634379
1390 2024856991
1391 2024947998
1392 2043097093
1393 2043208097
1394 2044336111
1395 2071073890
1396 2072437315
1397 2072531478
1398 2074727683
1399 2074729082
1400 2120319722
1401 2120459676
1402 2120554561
1403 2120638523
1404 2157871238
1405 2157996131
1406 2159123370
1407 2164779731
1408 2183293482
1409 2183294891
1410 2202119072
1411 2202206201
1412 2203612922
1413 2206351912
1414 2208370590
1415 2208497234
1416 2222389405
1417 2222483949
1418 2222580918
1419 2226716880
1420 2236192062
1421 2237582035
1422 2247878852
1423 2247880275
1424 2256915609
1425 2278091354
1426 2279242239
1427 2279243666
1428 2321619934
1429 2321621363
1430 2347243170
1431 2358468473
1432 2364076895
1433 2364078328
1434 2366446151
1435 2373730207
1436 2375213808
1437 2375361005
1438 2375460758
1439 2375462197
1440 2442127948
1441 2442227624
1442 2444374779
1443 2448273334
1444 2451770004
1445 2453635025
1446 2456070949
1447 2456072396
1448 2461846992
1449 2491075043
1450 2499709967
1451 2499711418
1452 2522056873
1453 2522058326
1454 2522160150
1455 2529447852
1456 2570017678
1457 2570106472
1458 2589926774
1459 2589928233
1460 2600545124
1461 2600697239
1462 2602007172
1463 2608853791
1464 2624814711
1465 2624950383
1466 2625054050
1467 2628099444
1468 2629675740
1469 2629777052
1470 2692066135
1471 2692067606
1472 2708171220
1473 2708325779
1474 2710025616
1475 2711861051
1476 2733122324
1477 2733247056
1478 2733352330
1479 2737017436
1480 2759247193
1481 2759248674
1482 2776680353
1483 2776681836
1484 2787351966
1485 2856722122
1486 2856828673
1487 2856830160
1488 2880740741
1489 2880742230
1490 2883500737
1491 2890373793
1492 2892032608
1493 2892034101
1494 2904364210
1495 2910705290
1496 2935521819
1497 2935681523
1498 2938097837
1499 2938099336
1500 2984247540