0 1
1 1
2 1
3 2
4 2
5 2
6 4
7 4
8 4
9 6
10 7
11 7
12 10
13 11
14 11
15 15
16 17
17 17
18 22
19 24
20 25
21 32
22 35
23 36
24 44
25 48
26 50
27 60
28 66
29 68
30 81
31 89
32 92
33 107
34 117
35 121
36 141
37 153
38 159
39 181
40 197
41 205
42 233
43 252
44 262
45 295
46 320
47 332
48 372
49 401
50 417
51 465
52 501
53 520
54 575
55 619
56 645
57 710
58 763
59 793
60 869
61 933
62 971
63 1059
64 1134
65 1180
66 1286
67 1374
68 1430
69 1549
70 1654
71 1722
72 1863
73 1985
74 2065
75 2225
76 2372
77 2467
78 2654
79 2821
80 2934
81 3149
82 3345
83 3478
84 3724
85 3949
86 4109
87 4391
88 4652
89 4835
90 5157
91 5460
92 5676
93 6043
94 6390
95 6638
96 7059
97 7457
98 7747
99 8220
100 8676
101 9013
102 9553
103 10071
104 10459
105 11066
106 11662
107 12108
108 12798
109 13468
110 13980
111 14760
112 15526
113 16110
114 16988
115 17850
116 18522
117 19509
118 20487
119 21247
120 22357
121 23463
122 24333
123 25576
124 26818
125 27800
126 29200
127 30598
128 31715
129 33274
130 34842
131 36106
132 37856
133 39614
134 41039
135 42985
136 44962
137 46567
138 48742
139 50944
140 52750
141 55173
142 57641
143 59668
144 62361
145 65102
146 67386
147 70379
148 73440
149 75989
150 79312
151 82716
152 85575
153 89258
154 93039
155 96222
156 100316
157 104514
158 108070
159 112587
160 117239
161 121202
162 126209
163 131361
164 135769
165 141286
166 146996
167 151897
168 157996
169 164294
170 169732
171 176459
172 183424
173 189450
174 196860
175 204528
176 211216
177 219377
178 227840
179 235222
180 244193
181 253511
182 261686
183 271544
184 281795
185 290803
186 301643
187 312909
188 322859
189 334736
190 347103
191 358069
192 371113
193 384680
194 396750
195 411019
196 425909
197 439188
198 454830
199 471126
200 485710
201 502821
202 520680
203 536693
204 555400
205 574912
206 592496
207 612935
208 634279
209 653536
210 675846
211 699159
212 720277
213 744619
214 770063
215 793143
216 819705
217 847460
218 872723
219 901647
220 931895
221 959495
222 991021
223 1023968
224 1054109
225 1088385
226 1124275
227 1157169
228 1194475
229 1233493
230 1269354
231 1309903
232 1352355
233 1391434
234 1435490
235 1481575
236 1524149
237 1571991
238 1622064
239 1668371
240 1720281
241 1774621
242 1825011
243 1881310
244 1940253
245 1994976
246 2056031
247 2119938
248 2179411
249 2245526
250 2314749
251 2379298
252 2450932
253 2525893
254 2595932
255 2673413
256 2754567
257 2830507
258 2914362
259 3002116
260 3084393
261 3175049
262 3269971
263 3359075
264 3457050
265 3559570
266 3656046
267 3761882
268 3872659
269 3977000
270 4091243
271 4210816
272 4323683
273 4446970
274 4576004
275 4697925
276 4830943
277 4970113
278 5101847
279 5245221
280 5395228
281 5537433
282 5692007
283 5853652
284 6007110
285 6173540
286 6347674
287 6513190
288 6692449
289 6879883
290 7058295
291 7251200
292 7452959
293 7645206
294 7852750
295 8069691
296 8276787
297 8499984
298 8733296
299 8956199
300 9196093
301 9446820
302 9686747
303 9944526
304 10213906
305 10471875
306 10748777
307 11038064
308 11315480
309 11612733
310 11923246
311 12221349
312 12540444
313 12873636
314 13193886
315 13536115
316 13893538
317 14237428
318 14604528
319 14987710
320 15356787
321 15750290
322 16161067
323 16557059
324 16978784
325 17418788
326 17843514
327 18295288
328 18766629
329 19221916
330 19705673
331 20210277
332 20698283
333 21216140
334 21756222
335 22278880
336 22833084
337 23410920
338 23970719
339 24563526
340 25181486
341 25780677
342 26414718
343 27075418
344 27716642
345 28394322
346 29100522
347 29786442
348 30510770
349 31265243
350 31998670
351 32772432
352 33578395
353 34362411
354 35188818
355 36049227
356 36887059
357 37769375
358 38687902
359 39582854
360 40524518
361 41504577
362 42460385
363 43465136
364 44510653
365 45530847
366 46602626
367 47717593
368 48806447
369 49949244
370 51137844
371 52299394
372 53517765
373 54784570
374 56023439
375 57321667
376 58671432
377 59992284
378 61375543
379 62813172
380 64220958
381 65694154
382 67225131
383 68725172
384 70293863
385 71923439
386 73521336
387 75191191
388 76925609
389 78627118
390 80404076
391 82249290
392 84060828
393 85951336
394 87914081
395 89841847
396 91852624
397 93939723
398 95990979
399 98128976
400 100347645
401 102529407
402 104802335
403 107160332
404 109480446
405 111895747
406 114401182
407 116867659
408 119434066
409 122095361
410 124716644
411 127442530
412 130268904
413 133054058
414 135948851
415 138949344
416 141907863
417 144981135
418 148166149
419 151307870
420 154569740
421 157949410
422 161285106
423 164746416
424 168332020
425 171872254
426 175544301
427 179347340
428 183104242
429 186998811
430 191031435
431 195016837
432 199146697
433 203421857
434 207648923
435 212026732
436 216557979
437 221040139
438 225680276
439 230481677
440 235233082
441 240149650
442 245236461
443 250272221
444 255480870
445 260868251
446 266204101
447 271720743
448 277425797
449 283078174
450 288919654
451 294959271
452 300945886
453 307130060
454 313522823
455 319861380
456 326406924
457 333171837
458 339882200
459 346808560
460 353965608
461 361067415
462 368395535
463 375965998
464 383480887
465 391231769
466 399237795
467 407187789
468 415384813
469 423849547
470 432257933
471 440924367
472 449872631
473 458764071
474 467925355
475 477382090
476 486782303
477 496464457
478 506457346
479 516393246
480 526623705
481 537180297
482 547680597
483 558488394
484 569638813
485 580732551
486 592147989
487 603923001
488 615642136
489 627696820
490 640128881
491 652505432
492 665233143
493 678356568
494 691425383
495 704860204
496 718710706
497 732507434
498 746686886
499 761301865
500 775864142
501 790825802
502 806244938
503 821612398
504 837397085
505 853660694
506 869874714
507 886524272
508 903676423
509 920780208
510 938338651
511 956423660
512 974463093
513 992976872
514 1012042753
515 1031064485
516 1050581914
517 1070677816
518 1090732694
519 1111304348
520 1132482075
521 1153621366
522 1175300797
523 1197614789
524 1219893857
525 1242735611
526 1266242630
527 1289718274
528 1313781686
529 1338541070
530 1363273016
531 1388617867
532 1414692322
533 1440743387
534 1467434256
535 1494887875
536 1522323488
537 1550426490
538 1579328542
539 1608217139
540 1637801901
541 1668222558
542 1698636397
543 1729776012
544 1761790647
545 1793803600
546 1826574184
547 1860260190
548 1893951999
549 1928433197
550 1963871920
551 1999323343
552 2035599035
553 2072875829
554 2110173647
555 2148329800
556 2187533589
557 2226766818
558 2266895847
559 2308119494
560 2349381747
561 2391577505
562 2434918854
563 2478308289
564 2522671354
565 2568230618
566 2613849365
567 2660482970
568 2708367737
569 2756322643
570 2805335353
571 2855655011
572 2906058287
573 2957563712
574 3010435216
575 3063402148
576 3117518611
577 3173062181
578 3228716117
579 3285567173
580 3343908942
581 3402375523
582 3462090986
583 3523363066
584 3584776497
585 3647489732
586 3711829446
587 3776327530
588 3842180992
589 3909731908
590 3977459451
591 4046598436
592 4117511085
593 4188619324
594 4261198611
595 4335627824
596 4410274231
597 4486453025
598 4564563902
599 4642912944
600 4722858179
601 4804819135
602 4887043125
603 4970929263
604 5056919592
605 5143196048
606 5231204582
607 5321408558
608 5411926173
609 5504246593
610 5598857479
611 5693809211
612 5790640008
613 5889859586
614 5989450310
615 6090995845
616 6195033963
617 6299474528
618 6405951962
619 6515027785
620 6624539164
621 6736170399
622 6850513012
623 6965325747
624 7082346347
625 7202192052
626 7322546049
627 7445198378
628 7570797500
629 7696942989
630 7825480920
631 7957089753
632 8089288402
633 8223976806
634 8361866895
635 8500388504
636 8641502656
637 8785953446
638 8931083581
639 9078910789
640 9230214973
641 9382246194
642 9537086400
643 9695548924
644 9854790841
645 10016953649
646 10182891629
647 10349663071
648 10519475635
649 10693219635
650 10867854188
651 11045651859
652 11227546946
653 11410392239
654 11596529638
655 11786932063
656 11978349274
657 12173191360
658 12372476940
659 12572842713
660 12776771480
661 12985325972
662 13195033156
663 13408446150
664 13626676563
665 13846130894
666 14069441304
667 14297766978
668 14527396113
669 14761034542
670 14999893754
671 15240136644
672 15484551996
673 15734400953
674 15985720614
675 16241376746
676 16502689354
677 16765562552
678 17032947572
679 17306217541
680 17581142720
681 17860758135
682 18146499985
683 18433995566
684 18726369479
685 19025114696
686 19325719179
687 19631395741
688 19943703258
689 20257977712
690 20577525423
691 20903969443
692 21232497909
693 21566507789
694 21907692568
695 22251078961
696 22600165000
697 22956713188
698 23315591493
699 23680392769
700 24052954435
701 24427976607
702 24809158496
703 25198409443
704 25590260845
705 25988510994
706 26395152727
707 26804539638
708 27220579622
709 27645342476
710 28073002310
711 28507574204
712 28951217680
713 29397916262
714 29851799461
715 30315108960
716 30781641652
717 31255639684
718 31739438362
719 32226632472
720 32721583436
721 33226718139
722 33735434042
723 34252208534
724 34779568084
725 35310695555
726 35850197024
727 36400697432
728 36955168088
729 37518336278
730 38092932916
731 38671705869
732 39259517621
733 39859202134
734 40463282809
735 41076748253
736 41702549724
737 42332974857
738 42973151171
739 43626139629
740 44283989711
741 44951964943
742 45633251992
743 46319648433
744 47016562851
745 47727298415
746 48443404746
747 49170433631
748 49911819570
749 50658845164
750 51417213310
751 52190487533
752 52969688701
753 53760666753
754 54567124883
755 55379800829
756 56204706747
757 57045684665
758 57893192772
759 58753396351
760 59630285470
761 60514023728
762 61410946908
763 62325190163
764 63246621094
765 64181734832
766 65134828882
767 66095460477
768 67070300085
769 68063799401
770 69065201738
771 70081349016
772 71116867130
773 72160668253
774 73219776778
775 74298982295
776 75386870100
777 76490644800
778 77615278402
779 78749006075
780 79899221787
781 81071077141
782 82252463348
783 83450959313
784 84671909911
785 85902835852
786 87151519114
787 88423497188
788 89705924010
789 91006774124
790 92331789527
791 93667738258
792 95022808526
793 96402944145
794 97794525012
795 99205939085
796 100643353428
797 102092742205
798 103562712607
799 105059646009
800 106569105888
801 108099913280
802 109658688553
803 111230563594
804 112824587226
805 114447606557
806 116084326070
807 117744019769
808 119433784706
809 121137869296
810 122865783846
811 124624872612
812 126398934814
813 128197711963
814 130028813174
815 131875555316
816 133747932208
817 135653818106
818 137576051949
819 139524867474
820 141508419058
821 143509043679
822 145537240113
823 147601440334
824 149683476653
825 151794096243
826 153942034799
827 156108598122
828 158304805608
829 160539686700
830 162794013626
831 165079071314
832 167404213955
833 169749654461
834 172126960475
835 174545796929
836 176985820983
837 179458879470
838 181974977486
839 184513181885
840 187085631913
841 189702669993
842 192342780369
843 195018388321
844 197740195793
845 200486063935
846 203268729283
847 206099254627
848 208954882899
849 211848647458
850 214791990298
851 217761505634
852 220770554122
853 223830955614
854 226918651836
855 230047310615
856 233229161594
857 236439466723
858 239692229417
859 243000078996
860 246337588466
861 249719088147
862 253157645351
863 256627112855
864 260142168435
865 263716301139
866 267322646708
867 270976226517
868 274690988046
869 278439308230
870 282236567761
871 286097169167
872 289992738526
873 293939008814
874 297950866315
875 301999136601
876 306099934575
877 310268633159
878 314475262206
879 318736301248
880 323067633272
881 327438454725
882 331865646033
883 336365600359
884 340906675904
885 345506129269
886 350180902203
887 354898481400
888 359676534171
889 364532540593
890 369433103816
891 374396290950
892 379440166951
893 384530412946
894 389685521181
895 394924123811
896 400210982003
897 405565008484
898 411005448268
899 416496091602
900 422056289785
901 427705897844
902 433407744042
903 439181609942
904 445047997036
905 450968711157
906 456963998250
907 463055010653
908 469202537167
909 475427268249
910 481751036477
911 488133566909
912 494596037900
913 501160963697
914 507786998824
915 514495780121
916 521310550642
917 528188853429
918 535152825351
919 542226428481
920 549366078091
921 556594396708
922 563936122991
923 571346498282
924 578848661247
925 586468107847
926 594158906005
927 601944704231
928 609851811749
929 617833062297
930 625912635899
931 634117652698
932 642399721627
933 650783544717
934 659297098229
935 667890692450
936 676589591458
937 685422635135
938 694338840582
939 703364010943
940 712527886716
941 721778133417
942 731141144006
943 740647564064
944 750243699281
945 759956497054
946 769817565530
947 779771800587
948 789846752979
949 800074983929
950 810399959126
951 820849815025
952 831458136277
953 842166902647
954 853004873132
955 864006634300
956 875112677684
957 886352377622
958 897761392127
959 909278651545
960 920934171026
961 932764678819
962 944707552840
963 956793437369
964 969060188067
965 981443541747
966 993974817983
967 1006693011365
968 1019532223115
969 1032524420599
970 1045709782771
971 1059020703949
972 1072489859592
973 1086158621237
974 1099957665985
975 1113920335261
976 1128089262037
977 1142393344553
978 1156866648851
979 1171553062014
980 1186379677460
981 1201381263786
982 1216603048188
983 1231970251258
984 1247518387720
985 1263294002596
986 1279220438658
987 1295333947564
988 1311682477952
989 1328187407781
990 1344885754579
991 1361826870224
992 1378930176741
993 1396233444468
994 1413787499851
995 1431509702570
996 1449438629086
997 1467626595876
998 1485988904588
999 1504564906450
1000 1523408465249