0 1
1 1
2 1
3 1
4 1
5 2
6 1
7 1
8 2
9 3
10 1
11 2
12 2
13 3
14 5
15 1
16 3
17 2
18 3
19 5
20 7
21 2
22 5
23 3
24 4
25 6
26 7
27 11
28 3
29 8
30 5
31 6
32 6
33 8
34 11
35 15
36 7
37 13
38 9
39 9
40 9
41 10
42 12
43 16
44 22
45 11
46 20
47 15
48 17
49 14
50 15
51 16
52 18
53 24
54 30
55 18
56 30
57 26
58 28
59 22
60 27
61 21
62 25
63 27
64 33
65 42
66 36
67 45
68 43
69 46
70 38
71 44
72 33
73 43
74 36
75 44
76 47
77 60
78 46
79 66
80 64
81 70
82 63
83 72
84 61
85 69
86 60
87 63
88 58
89 69
90 80
91 88
92 99
93 96
94 106
95 105
96 115
97 100
98 112
99 102
100 104
101 91
102 110
103 94
104 117
105 125
106 140
107 137
108 166
109 155
110 185
111 164
112 185
113 166
114 173
115 158
116 172
117 136
118 175
119 161
120 183
121 205
122 215
123 229
124 244
125 264
126 255
127 288
128 273
129 287
130 266
131 286
132 239
133 268
134 234
135 266
136 270
137 303
138 302
139 348
140 347
141 398
142 394
143 438
144 427
145 453
146 433
147 467
148 408
149 444
150 408
151 403
152 370
153 471
154 418
155 474
156 488
157 518
158 563
159 603
160 639
161 653
162 703
163 697
164 741
165 682
166 740
167 674
168 672
169 622
170 658
171 653
172 714
173 668
174 734
175 757
176 855
177 855
178 958
179 971
180 1049
181 1064
182 1135
183 1095
184 1172
185 1115
186 1142
187 1060
188 1101
189 974
190 1144
191 1018
192 1108
193 1062
194 1164
195 1192
196 1294
197 1358
198 1440
199 1533
200 1616
201 1700
202 1709
203 1802
204 1797
205 1842
206 1768
207 1833
208 1661
209 1731
210 1744
211 1708
212 1644
213 1784
214 1677
215 1823
216 1892
217 2033
218 2087
219 2286
220 2284
221 2524
222 2556
223 2739
224 2761
225 2891
226 2832
227 2950
228 2797
229 2897
230 2653
231 2931
232 2676
233 2800
234 2583
235 2830
236 2707
237 2869
238 2936
239 3150
240 3251
241 3478
242 3634
243 3800
244 4030
245 4126
246 4320
247 4406
248 4601
249 4516
250 4665
251 4468
252 4498
253 4589
254 4525
255 4321
256 4454
257 4258
258 4413
259 4364
260 4560
261 4630
262 4920
263 5011
264 5322
265 5531
266 5881
267 6048
268 6456
269 6627
270 6973
271 6975
272 7300
273 7192
274 7344
275 7042
276 7607
277 7045
278 7330
279 6947
280 7100
281 6782
282 7197
283 6852
284 7270
285 7296
286 7677
287 7742
288 8351
289 8437
290 8962
291 9371
292 9803
293 10180
294 10606
295 10963
296 11174
297 11475
298 11362
299 11580
300 11801
301 11709
302 11490
303 11577
304 11292
305 11369
306 11044
307 11362
308 11140
309 11457
310 11562
311 11987
312 12079
313 12787
314 12995
315 13834
316 14189
317 15118
318 15416
319 16386
320 16716
321 17390
322 17602
323 18162
324 17844
325 19068
326 18326
327 18839
328 18214
329 18710
330 17926
331 18466
332 17665
333 18220
334 17787
335 18418
336 18168
337 18984
338 18989
339 19732
340 20099
341 21141
342 21765
343 22886
344 23732
345 24743
346 25777
347 26578
348 27305
349 27787
350 28357
351 29332
352 29388
353 29439
354 29885
355 29417
356 29568
357 29231
358 29242
359 28745
360 29189
361 28614
362 29097
363 29231
364 29524
365 29850
366 30946
367 31136
368 32574
369 33577
370 34861
371 36142
372 37980
373 38802
374 40679
375 41719
376 43071
377 43432
378 45934
379 45466
380 46938
381 46435
382 47694
383 46654
384 47756
385 46338
386 47321
387 46004
388 47133
389 45782
390 46955
391 46164
392 47375
393 46727
394 48493
395 48513
396 50476
397 51412
398 53884
399 54986
400 57725
401 59381
402 61684
403 63714
404 65589
405 67087
406 70158
407 70897
408 72330
409 73672
410 74253
411 74821
412 74969
413 75453
414 74971
415 75230
416 74385
417 74877
418 74308
419 74530
420 73828
421 75206
422 74719
423 75888
424 76603
425 78691
426 79784
427 82747
428 84495
429 87733
430 90536
431 94132
432 96413
433 100205
434 102150
435 107358
436 108363
437 112283
438 113128
439 116690
440 116301
441 119705
442 118234
443 120746
444 119105
445 120924
446 118624
447 120959
448 118462
449 119885
450 118338
451 119732
452 118325
453 121109
454 119868
455 123573
456 124649
457 128086
458 129862
459 135617
460 137804
461 143227
462 146980
463 151898
464 155619
465 163291
466 165704
467 171140
468 175066
469 178750
470 181953
471 184997
472 187308
473 188416
474 190432
475 190558
476 191588
477 191318
478 191865
479 190604
480 191394
481 190466
482 190886
483 189633
484 191492
485 191657
486 194039
487 195731
488 199567
489 202382
490 208176
491 212219
492 218615
493 224506
494 231362
495 236708
496 247453
497 251931
498 260778
499 265910
500 275151
501 278550
502 287476
503 288664
504 296246
505 296743
506 302569
507 300929
508 306239
509 303433
510 307682
511 303892
512 307163
513 303132
514 306472
515 302315
516 306095
517 304128
518 308838
519 307437
520 314789
521 315650
522 323429
523 327754
524 337830
525 342100
526 354497
527 360320
528 375702
529 382730
530 395878
531 405087
532 418426
533 426653
534 437824
535 446141
536 455361
537 462628
538 468881
539 474636
540 478704
541 482557
542 483924
543 487774
544 486662
545 488398
546 487280
547 487716
548 486115
549 487938
550 485645
551 489036
552 490743
553 493899
554 497858
555 506125
556 510504
557 520800
558 531484
559 541494
560 553023
561 572496
562 581726
563 601399
564 615879
565 634704
566 647358
567 669665
568 679470
569 700026
570 709019
571 726757
572 731991
573 749371
574 751095
575 764300
576 764590
577 774831
578 771768
579 779879
580 773927
581 781009
582 774843
583 780905
584 774417
585 782097
586 778244
587 787054
588 784079
589 798281
590 799373
591 815598
592 820972
593 841269
594 849253
595 878092
596 889385
597 917240
598 935227
599 964424
600 983590
601 1014633
602 1035242
603 1063306
604 1085454
605 1109936
606 1130138
607 1150708
608 1167640
609 1183963
610 1199210
611 1209323
612 1219996
613 1226988
614 1233894
615 1235755
616 1240420
617 1239230
618 1241976
619 1241346
620 1244050
621 1241695
622 1248582
623 1250393
624 1256940
625 1265685
626 1276868
627 1287924
628 1306023
629 1321971
630 1350157
631 1371542
632 1402484
633 1429050
634 1468113
635 1497800
636 1541029
637 1571796
638 1617357
639 1647104
640 1694502
641 1720106
642 1765445
643 1789342
644 1829490
645 1847564
646 1883326
647 1895157
648 1925938
649 1930625
650 1954590
651 1955975
652 1972675
653 1966533
654 1983378
655 1973962
656 1987363
657 1979321
658 1991371
659 1983866
660 2004246
661 1996349
662 2021780
663 2024120
664 2050999
665 2058723
666 2107101
667 2116994
668 2166918
669 2194309
670 2249913
671 2283321
672 2349538
673 2387900
674 2455067
675 2506429
676 2568654
677 2620192
678 2685521
679 2733932
680 2791567
681 2842356
682 2890812
683 2933354
684 2976004
685 3013164
686 3044144
687 3072647
688 3092652
689 3113544
690 3127389
691 3139889
692 3145174
693 3155775
694 3158702
695 3164673
696 3167553
697 3177274
698 3183624
699 3193764
700 3208508
701 3226923
702 3248175
703 3284720
704 3312034
705 3356624
706 3403000
707 3461429
708 3514105
709 3592257
710 3651615
711 3740847
712 3809287
713 3905712
714 3977808
715 4082376
716 4152789
717 4256127
718 4325818
719 4424269
720 4487451
721 4580787
722 4632752
723 4717877
724 4759466
725 4828631
726 4856258
727 4915631
728 4929395
729 4975697
730 4979182
731 5017392
732 5009032
733 5044806
734 5030271
735 5062131
736 5052600
737 5087510
738 5073609
739 5123907
740 5117382
741 5179888
742 5189704
743 5265328
744 5288411
745 5385164
746 5428543
747 5538518
748 5607314
749 5730720
750 5815228
751 5956341
752 6056416
753 6201403
754 6315976
755 6461222
756 6583026
757 6726521
758 6847186
759 6983331
760 7104217
761 7224854
762 7334356
763 7442320
764 7535405
765 7621339
766 7700989
767 7765186
768 7829258
769 7874432
770 7918625
771 7953562
772 7981896
773 8005896
774 8031641
775 8040759
776 8065173
777 8088701
778 8101351
779 8129095
780 8175618
781 8203434
782 8258494
783 8323476
784 8393446
785 8472855
786 8590116
787 8680099
788 8824644
789 8952321
790 9114973
791 9259208
792 9460804
793 9613932
794 9829719
795 10003793
796 10225730
797 10402856
798 10635767
799 10803912
800 11031486
801 11204568
802 11413101
803 11560161
804 11760870
805 11884089
806 12053528
807 12155541
808 12299299
809 12370363
810 12494412
811 12535341
812 12636492
813 12656571
814 12741714
815 12745172
816 12820962
817 12812850
818 12891053
819 12871749
820 12976954
821 12964619
822 13071653
823 13086057
824 13223969
825 13262681
826 13436383
827 13509091
828 13711981
829 13837162
830 14075233
831 14234242
832 14510280
833 14708806
834 15006640
835 15247215
836 15564615
837 15826185
838 16155359
839 16437230
840 16773641
841 17059974
842 17383606
843 17673435
844 17974060
845 18239410
846 18515100
847 18760148
848 18995880
849 19204364
850 19403698
851 19577412
852 19735346
853 19874906
854 19996154
855 20095736
856 20198662
857 20270915
858 20339876
859 20403923
860 20466990
861 20525047
862 20590530
863 20656160
864 20733326
865 20834615
866 20932814
867 21070039
868 21211883
869 21400627
870 21580073
871 21835299
872 22060436
873 22372913
874 22654623
875 23029346
876 23352878
877 23782873
878 24143886
879 24610949
880 25012956
881 25512139
882 25929948
883 26457018
884 26878440
885 27397430
886 27818585
887 28314751
888 28698718
889 29176004
890 29523930
891 29951870
892 30252301
893 30631456
894 30875442
895 31201559
896 31382595
897 31675373
898 31790827
899 32035845
900 32118371
901 32319045
902 32355770
903 32573650
904 32566697
905 32772633
906 32789522
907 32993833
908 33024516
909 33293333
910 33344085
911 33656541
912 33795903
913 34150853
914 34355138
915 34805097
916 35082189
917 35596220
918 35980257
919 36549325
920 37012685
921 37666409
922 38194989
923 38892181
924 39510622
925 40236838
926 40900465
927 41666303
928 42335058
929 43088779
930 43790949
931 44505545
932 45166579
933 45864966
934 46476576
935 47098884
936 47667004
937 48211022
938 48707297
939 49180466
940 49593015
941 49988006
942 50322918
943 50648806
944 50906720
945 51170635
946 51393548
947 51601576
948 51774685
949 51974511
950 52142028
951 52326780
952 52534932
953 52737691
954 52990366
955 53249287
956 53584241
957 53901138
958 54357709
959 54759516
960 55313571
961 55836308
962 56514488
963 57135312
964 57938593
965 58656857
966 59571662
967 60411133
968 61425888
969 62353968
970 63454427
971 64438990
972 65596907
973 66607839
974 67774250
975 68810474
976 69970781
977 70950731
978 72085372
979 73019524
980 74070421
981 74914823
982 75891951
983 76632022
984 77498511
985 78130500
986 78907914
987 79388785
988 80083924
989 80444302
990 81042660
991 81323119
992 81842503
993 82012453
994 82526787
995 82652347
996 83135267
997 83265118
998 83783030
999 83942724
1000 84527031
1001 84756678
1002 85431770
1003 85797857
1004 86579177
1005 87074331
1006 88012667
1007 88678778
1008 89750169
1009 90603384
1010 91828937
1011 92856504
1012 94261396
1013 95458060
1014 96980273
1015 98363401
1016 99987158
1017 101468855
1018 103206549
1019 104752428
1020 106489540
1021 108122073
1022 109841781
1023 111437889
1024 113137703
1025 114675453
1026 116279965
1027 117719904
1028 119206442
1029 120531196
1030 121867320
1031 123031070
1032 124230523
1033 125218948
1034 126247035
1035 127118791
1036 127949368
1037 128661301
1038 129411165
1039 129971329
1040 130598128
1041 131142881
1042 131659174
1043 132181077
1044 132716572
1045 133246337
1046 133808111
1047 134476195
1048 135064764
1049 135879323
1050 136667741
1051 137625114
1052 138560870
1053 139779739
1054 140897261
1055 142345470
1056 143720124
1057 145417091
1058 147025362
1059 149013790
1060 150850798
1061 153048983
1062 155130896
1063 157497906
1064 159735581
1065 162314176
1066 164641834
1067 167291959
1068 169747473
1069 172401341
1070 174823618
1071 177520282
1072 179849461
1073 182449640
1074 184688924
1075 187149582
1076 189211341
1077 191511601
1078 193338794
1079 195449921
1080 197032441
1081 198955985
1082 200263441
1083 201949704
1084 203023375
1085 204533979
1086 205364414
1087 206747763
1088 207398315
1089 208652388
1090 209234651
1091 210441989
1092 210954074
1093 212220479
1094 212789273
1095 214113665
1096 214829703
1097 216311811
1098 217220471
1099 218935495
1100 220124218
1101 222063192
1102 223579848
1103 225856731
1104 227751332
1105 230338804
1106 232621316
1107 235599135
1108 238246628
1109 241511236
1110 244547763
1111 248083768
1112 251403959
1113 255211296
1114 258736750
1115 262690520
1116 266421570
1117 270443551
1118 274213091
1119 278250446
1120 282023260
1121 285962798
1122 289595630
1123 293403272
1124 296855650
1125 300414189
1126 303631164
1127 306903054
1128 309781717
1129 312759629
1130 315309411
1131 317913413
1132 320164508
1133 322430887
1134 324337576
1135 326330617
1136 328024351
1137 329716211
1138 331269274
1139 332783573
1140 334264671
1141 335687546
1142 337200752
1143 338640915
1144 340302882
1145 341854496
1146 343727062
1147 345520315
1148 347711331
1149 349795763
1150 352409599
1151 354934619
1152 357993434
1153 361053738
1154 364650518
1155 368131712
1156 372321163
1157 376351949
1158 380978059
1159 385563329
1160 390673198
1161 395648151
1162 401252402
1163 406551810
1164 412414239
1165 418075943
1166 424122727
1167 429862060
1168 436075023
1169 441835257
1170 448021235
1171 453657167
1172 459729079
1173 465151069
1174 470948699
1175 476036782
1176 481558905
1177 486136217
1178 491265088
1179 495383884
1180 500047615
1181 503631107
1182 507934651
1183 510911542
1184 514798803
1185 517398493
1186 520866434
1187 523049551
1188 526341896
1189 528223511
1190 531285828
1191 533120209
1192 536102565
1193 537961615
1194 541086687
1195 543046836
1196 546408072
1197 548749236
1198 552416562
1199 555244495
1200 559471992
1201 562852648
1202 567696902
1203 571909822
1204 577367519
1205 582298257
1206 588574461
1207 594260358
1208 601226501
1209 607798908
1210 615375596
1211 622625551
1212 630964052
1213 638752356
1214 647554019
1215 655952891
1216 665094143
1217 673767626
1218 683210911
1219 692019231
1220 701504902
1221 710387508
1222 719708831
1223 728376511
1224 737468038
1225 745772904
1226 754447060
1227 762241554
1228 770333906
1229 777540506
1230 784965749
1231 791537193
1232 798252061
1233 804143093
1234 810155650
1235 815440006
1236 820712596
1237 825536467
1238 830206363
1239 834554748
1240 838861615
1241 842968440
1242 846869813
1243 850972529
1244 854822453
1245 858943747
1246 862916538
1247 867384740
1248 871679851
1249 876692193
1250 881542515
1251 887319792
1252 892939390
1253 899539967
1254 906145110
1255 913735049
1256 921319116
1257 930076594
1258 938742069
1259 948557783
1260 958431865
1261 969301077
1262 980151571
1263 992139776
1264 1003910051
1265 1016733599
1266 1029339649
1267 1042914584
1268 1056095899
1269 1070186650
1270 1083760341
1271 1098146576
1272 1111786788
1273 1126310210
1274 1139817371
1275 1154086905
1276 1167224467
1277 1181093037
1278 1193522499
1279 1206879465
1280 1218433752
1281 1231015261
1282 1241618086
1283 1253366298
1284 1262864166
1285 1273734469
1286 1282185642
1287 1292143169
1288 1299633625
1289 1308742839
1290 1315359403
1291 1323822863
1292 1329793997
1293 1337672810
1294 1343204828
1295 1350826819
1296 1356201378
1297 1363760107
1298 1369273611
1299 1377044102
1300 1383113838
1301 1391447866
1302 1398228093
1303 1407539816
1304 1415361738
1305 1425634994
1306 1434945320
1307 1446510660
1308 1457120308
1309 1470405308
1310 1482588945
1311 1497197049
1312 1511282020
1313 1527456288
1314 1543012026
1315 1560865381
1316 1577906214
1317 1597015935
1318 1615531999
1319 1635805946
1320 1655320433
1321 1676680764
1322 1696997152
1323 1718912879
1324 1739721062
1325 1761923671
1326 1782901805
1327 1805028956
1328 1825687447
1329 1847450311
1330 1867504179
1331 1888476171
1332 1907726611
1333 1927569990
1334 1945757563
1335 1964428147
1336 1981251113
1337 1998441748
1338 2014166015
1339 2029685090
1340 2044101854
1341 2058327353
1342 2071457188
1343 2084263189
1344 2096466239
1345 2108170490
1346 2119542958
1347 2130375819
1348 2141245158
1349 2151624277
1350 2162387084
1351 2172671907
1352 2183765802
1353 2194510562
1354 2206268857
1355 2217884591
1356 2230866731
1357 2243625291
1358 2258063782
1359 2272680905
1360 2288859681
1361 2305306819
1362 2323852200
1363 2342390685
1364 2363066567
1365 2384156072
1366 2407041085
1367 2430423606
1368 2455872100
1369 2481328602
1370 2508948152
1371 2536738245
1372 2566198516
1373 2595681818
1374 2627035931
1375 2657930072
1376 2690512081
1377 2722448599
1378 2755892786
1379 2788216192
1380 2822113504
1381 2854343793
1382 2888168999
1383 2919775243
1384 2953109276
1385 2983595763
1386 3015908013
1387 3044950888
1388 3075904462
1389 3103038789
1390 3132479669
1391 3157676701
1392 3185083991
1393 3208242190
1394 3233821381
1395 3254855753
1396 3278654571
1397 3297735737
1398 3319725083
1399 3337324960
1400 3357904448
1401 3374087182
1402 3393660680
1403 3409181620
1404 3428186326
1405 3443424096
1406 3462532819
1407 3478357843
1408 3497939559
1409 3514789231
1410 3535759583
1411 3554128062
1412 3576882986
1413 3597669577
1414 3622576130
1415 3645939546
1416 3673908825
1417 3700253932
1418 3731233547
1419 3761097288
1420 3795328297
1421 3828536998
1422 3866351639
1423 3902894955
1424 3943968419
1425 3983963261
1426 4028167069
1427 4071052698
1428 4117984243
1429 4163541357
1430 4212827132
1431 4260191886
1432 4311230474
1433 4360001417
1434 4411901170
1435 4461435863
1436 4513666770
1437 4562914353
1438 4614827846
1439 4663463723
1440 4714085939
1441 4761457558
1442 4810240452
1443 4855809706
1444 4902161316
1445 4945502483
1446 4989238535
1447 5030048687
1448 5070664849
1449 5108898040
1450 5146515087
1451 5182106025
1452 5216667609
1453 5249831710
1454 5281838541
1455 5312722359
1456 5342523732
1457 5372006615
1458 5400153094
1459 5428638281
1460 5456094785
1461 5484253971
1462 5511931333
1463 5540720914
1464 5569039308
1465 5599577817
1466 5629718025
1467 5662202139
1468 5695446276
1469 5731010389
1470 5767200294
1471 5806957402
1472 5847239093
1473 5890919864
1474 5936135013
1475 5984564041
1476 6034313529
1477 6088097396
1478 6142830231
1479 6201359786
1480 6261213595
1481 6324759920
1482 6389096510
1483 6457136763
1484 6525778834
1485 6597633824
1486 6669664105
1487 6744937250
1488 6819456065
1489 6897182694
1490 6973257487
1491 7052731890
1492 7129102646
1493 7209173317
1494 7285206881
1495 7364632215
1496 7439169910
1497 7517533580
1498 7589614740
1499 7665594303
1500 7734760269