0 1
1 1
2 1
3 2
4 2
5 2
6 3
7 4
8 4
9 5
10 6
11 6
12 7
13 9
14 10
15 11
16 13
17 14
18 15
19 18
20 20
21 21
22 24
23 26
24 28
25 33
26 36
27 38
28 43
29 46
30 49
31 56
32 60
33 63
34 71
35 76
36 80
37 90
38 96
39 100
40 112
41 120
42 125
43 139
44 149
45 155
46 171
47 183
48 190
49 208
50 223
51 232
52 252
53 269
54 280
55 304
56 325
57 338
58 364
59 387
60 403
61 434
62 462
63 481
64 515
65 547
66 570
67 609
68 646
69 672
70 716
71 759
72 790
73 840
74 889
75 925
76 981
77 1037
78 1079
79 1141
80 1205
81 1254
82 1323
83 1396
84 1453
85 1531
86 1614
87 1679
88 1765
89 1857
90 1932
91 2030
92 2135
93 2221
94 2329
95 2446
96 2544
97 2665
98 2797
99 2907
100 3041
101 3189
102 3314
103 3464
104 3630
105 3771
106 3937
107 4122
108 4281
109 4464
110 4670
111 4849
112 5052
113 5282
114 5483
115 5708
116 5963
117 6187
118 6435
119 6717
120 6968
121 7243
122 7556
123 7836
124 8138
125 8484
126 8796
127 9129
128 9512
129 9858
130 10224
131 10646
132 11030
133 11434
134 11900
135 12326
136 12769
137 13280
138 13751
139 14237
140 14800
141 15321
142 15853
143 16471
144 17046
145 17630
146 18308
147 18941
148 19580
149 20322
150 21020
151 21720
152 22531
153 23298
154 24063
155 24950
156 25793
157 26629
158 27597
159 28520
160 29433
161 30489
162 31500
163 32497
164 33649
165 34756
166 35842
167 37095
168 38305
169 39488
170 40853
171 42175
172 43461
173 44943
174 46386
175 47789
176 49400
177 50972
178 52496
179 54242
180 55955
181 57613
182 59506
183 61368
184 63168
185 65222
186 67247
187 69200
188 71423
189 73620
190 75740
191 78147
192 80531
193 82828
194 85430
195 88017
196 90507
197 93318
198 96119
199 98813
200 101851
201 104884
202 107798
203 111076
204 114356
205 117511
206 121050
207 124594
208 128000
209 131812
210 135643
211 139325
212 143433
213 147567
214 151538
215 155963
216 160425
217 164710
218 169471
219 174278
220 178901
221 184024
222 189202
223 194183
224 199689
225 205266
226 210633
227 216549
228 222547
229 228320
230 234678
231 241133
232 247344
233 254167
234 261102
235 267783
236 275107
237 282557
238 289735
239 297584
240 305586
241 313303
242 321717
243 330300
244 338580
245 347596
246 356806
247 365695
248 375350
249 385216
250 394751
251 405091
252 415664
253 425886
254 436945
255 448268
256 459225
257 471053
258 483172
259 494905
260 507552
261 520523
262 533087
263 546598
264 560463
265 573911
266 588349
267 603171
268 617555
269 632965
270 648801
271 664186
272 680637
273 697547
274 713984
275 731537
276 749595
277 767158
278 785876
279 805138
280 823894
281 843854
282 864403
283 884424
284 905688
285 927596
286 948965
287 971622
288 994969
289 1017755
290 1041884
291 1066760
292 1091057
293 1116743
294 1143228
295 1169124
296 1196466
297 1224665
298 1252251
299 1281327
300 1311334
301 1340719
302 1371646
303 1403567
304 1434843
305 1467718
306 1501666
307 1534956
308 1569895
309 1605973
310 1641386
311 1678510
312 1716851
313 1754511
314 1793934
315 1834662
316 1874701
317 1916562
318 1959812
319 2002352
320 2046782
321 2092701
322 2137898
323 2185041
324 2233765
325 2281764
326 2331775
327 2383468
328 2434425
329 2487448
330 2542270
331 2596359
332 2652577
333 2710698
334 2768073
335 2827651
336 2889259
337 2950118
338 3013243
339 3078511
340 3143035
341 3209902
342 3279045
343 3347441
344 3418238
345 3491454
346 3563934
347 3638883
348 3716392
349 3793163
350 3872482
351 3954518
352 4035826
353 4119750
354 4206536
355 4292613
356 4381391
357 4473193
358 4564297
359 4658168
360 4755242
361 4851643
362 4950889
363 5053514
364 5155477
365 5260369
366 5368838
367 5476670
368 5587505
369 5702102
370 5816101
371 5933193
372 6054250
373 6174741
374 6298397
375 6426234
376 6553556
377 6684128
378 6819097
379 6953583
380 7091416
381 7233886
382 7375919
383 7521383
384 7671716
385 7821673
386 7975164
387 8133774
388 8292061
389 8453957
390 8621244
391 8788290
392 8959039
393 9135444
394 9311668
395 9491697
396 9677677
397 9863559
398 10053341
399 10249352
400 10445357
401 10645377
402 10851933
403 11058571
404 11269316
405 11486923
406 11704726
407 11926741
408 12155947
409 12385443
410 12619265
411 12860637
412 13102421
413 13348635
414 13602745
415 13857402
416 14116617
417 14384096
418 14652257
419 14925079
420 15206559
421 15488884
422 15775992
423 16072151
424 16369296
425 16671356
426 16982903
427 17295607
428 17613346
429 17940989
430 18269974
431 18604139
432 18948662
433 19294717
434 19646068
435 20008248
436 20372185
437 20741556
438 21122232
439 21504869
440 21893092
441 22293137
442 22695381
443 23103351
444 23523645
445 23946386
446 24375027
447 24816536
448 25260750
449 25711000
450 26174685
451 26641369
452 27114254
453 27601150
454 28091324
455 28587869
456 29099043
457 29613814
458 30135123
459 30671661
460 31212134
461 31759344
462 32322430
463 32889798
464 33464071
465 34054889
466 34650373
467 35252960
468 35872782
469 36497639
470 37129806
471 37779942
472 38435526
473 39098618
474 39780405
475 40468078
476 41163494
477 41878374
478 42599594
479 43328754
480 44078177
481 44834442
482 45598887
483 46384411
484 47177261
485 47978535
486 48801757
487 49632838
488 50472594
489 51335157
490 52206138
491 53086075
492 53989735
493 54902394
494 55824257
495 56770790
496 57726958
497 58692615
498 59683915
499 60685473
500 61696816
501 62734825
502 63783776
503 64842817
504 65929545
505 67027926
506 68136738
507 69274312
508 70424280
509 71584990
510 72775583
511 73979367
512 75194243
513 76440150
514 77700039
515 78971381
516 80274969
517 81593395
518 82923649
519 84287355
520 85666796
521 87058476
522 88484876
523 89927946
524 91383646
525 92875379
526 94384782
527 95907243
528 97467087
529 99045594
530 100637615
531 102268443
532 103919001
533 105583536
534 107288302
535 109013907
536 110754000
537 112535819
538 114339640
539 116158433
540 118020498
541 119905801
542 121806606
543 123752267
544 125722413
545 127708619
546 129741348
547 131799882
548 133875054
549 135998418
550 138148964
551 140316781
552 142534543
553 144780917
554 147045175
555 149361186
556 151707326
557 154072005
558 156490301
559 158940262
560 161409462
561 163934228
562 166492281
563 169070284
564 171705813
565 174376323
566 177067570
567 179818387
568 182605940
569 185414992
570 188285731
571 191195060
572 194126715
573 197122232
574 200158220
575 203217400
576 206342719
577 209510483
578 212702330
579 215962612
580 219267408
581 222597256
582 225997930
583 229445252
584 232918581
585 236465203
586 240060734
587 243683297
588 247381691
589 251131281
590 254908984
591 258765165
592 262674943
593 266613946
594 270634111
595 274710376
596 278817071
597 283007710
598 287257033
599 291537974
600 295905746
601 300334930
602 304797007
603 309348868
604 313964913
605 318615187
606 323358330
607 328168559
608 333014402
609 337956232
610 342968174
611 348017216
612 353165481
613 358386969
614 363647048
615 369009708
616 374448876
617 379928212
618 385513564
619 391178750
620 396885766
621 402702388
622 408602336
623 414545825
624 420602551
625 426746229
626 432935285
627 439241337
628 445638086
629 452082057
630 458646925
631 465306418
632 472015088
633 478848640
634 485780811
635 492764213
636 499876668
637 507091912
638 514360507
639 521762368
640 529271355
641 536835950
642 544538185
643 552352017
644 560223741
645 568237627
646 576367799
647 584558263
648 592895515
649 601353822
650 609874961
651 618547720
652 627346509
653 636210734
654 645231464
655 654383381
656 663603522
657 672985238
658 682503463
659 692092717
660 701848793
661 711746942
662 721719077
663 731863401
664 742155473
665 752524636
666 763071589
667 773772190
668 784553081
669 795517420
670 806641541
671 817849362
672 829246506
673 840809736
674 852460113
675 864305876
676 876324320
677 888433535
678 900744359
679 913234580
680 925819375
681 938612255
682 951591515
683 964669255
684 977961647
685 991447665
686 1005036325
687 1018846431
688 1032857622
689 1046975659
690 1061322160
691 1075877533
692 1090544182
693 1105446486
694 1120565601
695 1135800619
696 1151278780
697 1166981981
698 1182805861
699 1198880480
700 1215188685
701 1231622622
702 1248315159
703 1265250054
704 1282315806
705 1299648279
706 1317232289
707 1334952534
708 1352947816
709 1371203968
710 1389601972
711 1408283660
712 1427235920
713 1446335826
714 1465728198
715 1485401176
716 1505227931
717 1525356228
718 1545775445
719 1566354658
720 1587244799
721 1608436619
722 1629794959
723 1651473831
724 1673465345
725 1695630164
726 1718125514
727 1740944881
728 1763944567
729 1787284924
730 1810961068
731 1834824917
732 1859039921
733 1883602801
734 1908360919
735 1933481020
736 1958961599
737 1984645282
738 2010702032
739 2037132082
740 2063773441
741 2090799407
742 2118211987
743 2145844324
744 2173872981
745 2202301992
746 2230959653
747 2260025744
748 2289506331
749 2319224624
750 2349363850
751 2379932280
752 2410747882
753 2441997199
754 2473690717
755 2505641256
756 2538038821
757 2570896120
758 2604020597
759 2637605598
760 2671666371
761 2706004995
762 2740818127
763 2776123507
764 2811717613
765 2847800632
766 2884393036
767 2921285507
768 2958681656
769 2996604656
770 3034839521
771 3073593406
772 3112892245
773 3152515095
774 3192672533
775 3233393584
776 3274451414
777 3316059948
778 3358251284
779 3400792401
780 3443900823
781 3487611951
782 3531686434
783 3576345243
784 3621627076
785 3667286336
786 3713547604
787 3760452908
788 3807750143
789 3855667342
790 3904250268
791 3953240322
792 4002868921
793 4053185514
794 4103924734
795 4155321613
796 4207429614
797 4259976405
798 4313200468
799 4367159216
800 4421573506
801 4476685413
802 4532556389
803 4588900169
804 4645962263
805 4703808544
806 4762145699
807 4821222571
808 4881109439
809 4941505586
810 5002663476
811 5064658129
812 5127181263
813 5190488731
814 5254660268
815 5319380133
816 5384907755
817 5451327674
818 5518316413
819 5586136730
820 5654878419
821 5724210316
822 5794398431
823 5865537758
824 5937289134
825 6009922075
826 6083537179
827 6157787056
828 6232944514
829 6309115671
830 6385945081
831 6463709028
832 6542519318
833 6622012081
834 6702466818
835 6784001461
836 6866243830
837 6949476515
838 7033823602
839 7118904212
840 7205004300
841 7292254493
842 7380265047
843 7469324993
844 7559571460
845 7650605989
846 7742720917
847 7836059999
848 7930215724
849 8025483406
850 8122013945
851 8219390860
852 8317912361
853 8417736474
854 8518437364
855 8620316364
856 8723539129
857 8827670240
858 8933013871
859 9039743226
860 9147413528
861 9256331977
862 9366679528
863 9478001631
864 9590608162
865 9704688320
866 9819777983
867 9936189582
868 10054120598
869 10173096838
870 10293433552
871 10415336985
872 10538322718
873 10662708488
874 10788709281
875 10915830603
876 11044392902
877 11174620091
878 11306007231
879 11438877035
880 11573462960
881 11709249783
882 11846562366
883 11985643688
884 12125967791
885 12267861891
886 12411579084
887 12556582492
888 12703201362
889 12851698795
890 13001527213
891 13153018087
892 13306444796
893 13461248606
894 13617762788
895 13776271591
896 13936205370
897 14097899011
898 14261647700
899 14426870306
900 14593903567
901 14763054217
902 14933729544
903 15106267715
904 15280986959
905 15457283142
906 15635496090
907 15815955763
908 15998046248
909 16182108497
910 16368484889
911 16556547920
912 16746639523
913 16939114495
914 17133333211
915 17329638788
916 17528399187
917 17728962483
918 17931672546
919 18136910372
920 18344011978
921 18553322172
922 18765235374
923 18979075102
924 19195186528
925 19413978137
926 19634761255
927 19857881194
928 20083760595
929 20311697977
930 20542039035
931 20775221276
932 21010530326
933 21248311744
934 21489017832
935 21731921489
936 21977368409
937 22225826041
938 22476554177
939 22729897939
940 22986340704
941 23245129397
942 23506608375
943 23771277000
944 24038368776
945 24308227435
946 24581369180
947 24857013942
948 25135504305
949 25417373145
950 25701827132
951 25989207920
952 26280065525
953 26573592869
954 26870129948
955 27170244638
956 27473116484
957 27779083592
958 28088731876
959 28401226806
960 28716904755
961 29036370513
962 29358775419
963 29684453481
964 30014028318
965 30346637380
966 30682612561
967 31022596724
968 31365713047
969 31712290424
970 32062991822
971 32416926500
972 32774420159
973 33136155944
974 33501228554
975 33869960572
976 34243056324
977 34619595816
978 34999897927
979 35384688002
980 35773031702
981 36165244376
982 36562072971
983 36962568292
984 37367041238
985 37776261197
986 38189264641
987 38606357719
988 39028332463
989 39454210228
990 39884292485
991 40319394883
992 40758523710
993 41201975064
994 41650588123
995 42103354357
996 42560564725
997 43023082451
998 43489883790
999 43961253522
1000 44438079913