2 2
3 4
4 8
5 12
6 20
7 28
8 44
9 59
10 89
11 115
12 167
13 209
14 293
15 357
16 485
17 578
18 764
19 894
20 1154
21 1330
22 1682
23 1914
24 2378
25 2677
26 3275
27 3653
28 4409
29 4879
30 5819
31 6395
32 7547
33 8244
34 9638
35 10472
36 12140
37 13128
38 15104
39 16264
40 18584
41 19935
42 22637
43 24199
44 27323
45 29117
46 32705
47 34753
48 38849
49 41174
50 45824
51 48450
52 53702
53 56654
54 62558
55 65862
56 72470
57 76153
58 83519
59 87609
60 95789
61 100315
62 109367
63 114359
64 124343
65 129832
66 140810
67 146828
68 158864
69 165444
70 178604
71 185780
72 200132
73 207939
74 223553
75 232027
76 248975
77 258153
78 276509
79 286429
80 306269
81 316970
82 338372
83 349894
84 372938
85 385322
86 410090
87 423378
88 449954
89 464189
90 492659
91 507885
92 538337
93 554599
94 587123
95 604467
96 639155
97 657628
98 694574
99 714224
100 753524
101 774400
102 816152
103 838304
104 882608
105 906087
106 953045
107 977903
108 1027619
109 1053909
110 1106489
111 1134265
112 1189817
113 1219134
114 1277768
115 1308682
116 1370510
117 1403078
118 1468214
119 1502494
120 1571054
121 1607105
122 1679207
123 1717089
124 1792853
125 1832627
126 1912175
127 1953903
128 2037359
129 2081104
130 2168594
131 2214420
132 2306072
133 2354044
134 2449988
135 2500172
136 2600540
137 2653003
138 2757929
139 2812739
140 2922359
141 2979585
142 3094037
143 3153749
144 3273173
145 3335442
146 3459980
147 3524878
148 3654674
149 3722274
150 3857474
151 3927850
152 4068602
153 4141829
154 4288283
155 4364437
156 4516745
157 4595903
158 4754219
159 4836459
160 5000939
161 5086340
162 5257142
163 5345784
164 5523068
165 5615032
166 5798960
167 5894328
168 6085064
169 6183919
170 6381629
171 6484055
172 6688907
173 6794989
174 7007153
175 7116977
176 7336625
177 7450278
178 7677584
179 7795154
180 8030294
181 8151870
182 8395022
183 8520694
184 8772038
185 8901897
186 9161615
187 9295753
188 9564029
189 9702539
190 9979559
191 10122535
192 10408487
193 10556024
194 10851098
195 11003292
196 11307680
197 11464628
198 11778524
199 11940324
200 12263924
201 12430675
202 12764177
203 12935979
204 13279583
205 13456537
206 13810445
207 13992653
208 14357069
209 14544634
210 14919764
211 15112790
212 15498842
213 15697434
214 16094618
215 16298882
216 16707410
217 16917453
218 17337539
219 17553469
220 17985329
221 18207255
222 18651107
223 18879139
224 19335203
225 19569452
226 20037950
227 20278528
228 20759684
229 21006704
230 21500744
231 21754320
232 22261472
233 22521719
234 23042213
235 23309247
236 23843315
237 24117253
238 24665129
239 24946089
240 25508009
241 25796110
242 26372312
243 26667674
244 27258398
245 27561142
246 28166630
247 28476878
248 29097374
249 29415249
250 30050999
251 30376625
252 31027877
253 31361379
254 32028383
255 32369887
256 33052895
257 33402528
258 34101794
259 34459684
260 35175464
261 35541740
262 36274292
263 36649084
264 37398668
265 37782107
266 38548985
267 38941203
268 39725639
269 40126769
270 40929029
271 41339205
272 42159557
273 42578914
274 43417628
275 43846302
276 44703650
277 45141778
278 46018034
279 46465754
280 47361194
281 47818645
282 48733547
283 49200869
284 50135513
285 50612847
286 51567515
287 52055003
288 53029979
289 53527764
290 54523334
291 55031560
292 56048012
293 56566824
294 57604448
295 58133992
296 59193080
297 59733503
298 60814349
299 61365799
300 62468699
301 63031325
302 64156577
303 64730529
304 65878433
305 66463862
306 67634720
307 68231778
308 69425894
309 70034734
310 71252414
311 71873190
312 73114742
313 73747609
314 75013343
315 75658457
316 76948685
317 77606203
318 78921239
319 79591319
320 80931479
321 81614280
322 82979882
323 83675564
324 85066928
325 85775652
326 87193100
327 87915028
328 89358884
329 90094179
330 91564769
331 92313595
332 93811247
333 94573769
334 96098813
335 96875197
336 98427965
337 99218378
338 100799204
339 101603814
340 103213034
341 104032010
342 105669962
343 106503474
344 108170498
345 109018717
346 110715155
347 111578253
348 113304449
349 114182599
350 115938899
351 116832275
352 118619027
353 119527804
354 121345358
355 122269712
356 124118420
357 125058528
358 126938744
359 127894784
360 129806864
361 130779015
362 132723317
363 133711759
364 135688643
365 136693557
366 138703385
367 139724953
368 141768089
369 142806494
370 144883304
371 145938730
372 148049582
373 149122214
374 151267478
375 152357502
376 154537550
377 155645153
378 157860359
379 158985729
380 161236469
381 162379795
382 164666447
383 165827919
384 168150863
385 169330672
386 171690290
387 172888628
388 175285304
389 176502364
390 178936484
391 180172460
392 182644412
393 183899499
394 186409673
395 187684067
396 190232855
397 191526753
398 194114549
399 195428149
400 198055349
401 199388850
402 202055852
403 203409454
404 206116658
405 207490562
406 210238370
407 211632778
408 214421594
409 215836709
410 218666939
411 220102965
412 222975017
413 224432159
414 227346443
415 228824907
416 231781835
417 233281828
418 236281814
419 237803544
420 240847004
421 242390680
422 245478032
423 247043864
424 250175528
425 251763727
426 254940125
427 256550903
428 259772459
429 261406029
430 264673169
431 266329745
432 269642897
433 271322694
434 274682288
435 276385522
436 279791990
437 281518878
438 284972654
439 286723414
440 290224934
441 291999785
442 295549487
443 297348649
444 300946973
445 302770667
446 306418055
447 308266503
448 311963399
449 313836824
450 317583674
451 319482300
452 323279552
453 325203604
454 329051708
455 331001412
456 334900820
457 336876403
458 340827569
459 342829259
460 346832639
461 348860665
462 352916717
463 354971309
464 359080493
465 361161882
466 365324660
467 367433078
468 371649914
469 373785594
470 378056954
471 380220130
472 384546482
473 386737389
474 391119203
475 393338077
476 397775825
477 400022903
478 404517059
479 406792579
480 411343619
481 413647820
482 418256222
483 420589344
484 425255588
485 427617872
486 432342440
487 434734128
488 439517504
489 441938839
490 446781509
491 449232735
492 454135187
493 456616549
494 461579273
495 464091017
496 469114505
497 471656878
498 476741624
499 479314874
500 484461374
501 487065750
502 492274502
503 494910254
504 500181758
505 502849137
506 508183895
507 510883153
508 516281669
509 519013059
510 524475839
511 527239615
512 532767167
513 535563584
514 541156418
515 543985732
516 549644360
517 552506828
518 558231764
519 561127644
520 566919404
521 569848955
522 575708057
523 578671539
524 584598503
525 587596177
526 593591525
527 596623653
528 602687909
529 605754754
530 611888444
531 614990270
532 621193922
533 624330994
534 630605138
535 633777722
536 640122890
537 643331253
538 649747979
539 652992389
540 659481209
541 662761935
542 669323387
543 672640699
544 679275323
545 682629492
546 689337830
547 692729128
548 699511724
549 702940424
550 709797824
551 713264200
552 720196952
553 723701279
554 730709933
555 734252487
556 741337595
557 744918653
558 752080769
559 755700609
560 762940289
561 766599190
562 773916992
563 777615234
564 785011718
565 788749582
566 796225310
567 800003078
568 807558614
569 811376569
570 819012479
571 822870905
572 830587757
573 834486939
574 842285303
575 846225527
576 854105975
577 858087528
578 866050634
579 870073804
580 878120144
581 882185220
582 890315372
583 894422644
584 902637188
585 906786947
586 915086465
587 919279003
588 927664079
589 931899689
590 940370909
591 944649885
592 953207837
593 957530474
594 966175748
595 970542342
596 979275530
597 983686378
598 992508074
599 996963474
600 1005874274
601 1010374525
602 1019375027
603 1023920429
604 1033011233
605 1037602087
606 1046783795
607 1051420403
608 1060693619
609 1065376284
610 1074741614
611 1079470640
612 1088928692
613 1093704384
614 1103255768
615 1108078432
616 1117723760
617 1122593703
618 1132333589
619 1137251119
620 1147086179
621 1152051605
622 1161982457
623 1166996089
624 1177023353
625 1182085502
626 1192209800
627 1197320778
628 1207542734
629 1212702854
630 1223023094
631 1228232670
632 1238651822
633 1243911169
634 1254429863
635 1259739297
636 1270358165
637 1275718003
638 1286437679
639 1291848239
640 1302669359
641 1308130960
642 1319054162
643 1324567124
644 1335593048
645 1341157692
646 1352286980
647 1357903628
648 1369136924
649 1374805899
650 1386143849
651 1391865475
652 1403308727
653 1409083329
654 1420632533
655 1426460437
656 1438116245
657 1443997778
658 1455760844
659 1461696334
660 1473567314
661 1479557090
662 1491536642
663 1497581034
664 1509669818
665 1515769157
666 1527967835
667 1534122453
668 1546431689
669 1552641919
670 1565062379
671 1571328555
672 1583860907
673 1590183364
674 1602828278
675 1609207352
676 1621965500
677 1628401528
678 1641273584
679 1647766904
680 1660753544
681 1667304495
682 1680406397
683 1687015319
684 1700233163
685 1706900397
686 1720234865
687 1726960753
688 1740412529
689 1747197414
690 1760767184
691 1767611410
692 1781299862
693 1788203774
694 1802011598
695 1808975542
696 1822903430
697 1829927753
698 1843976399
699 1851061449
700 1865231549
701 1872377675
702 1886669927
703 1893877479
704 1908292583
705 1915561912
706 1930100570
707 1937432028
708 1952094944
709 1959488884
710 1974276764
711 1981733540
712 1996647092
713 2004167059
714 2019206993
715 2026790507
716 2041957535
717 2049604953
718 2064899789
719 2072611469
720 2088034829
721 2095811130
722 2111363732
723 2119205014
724 2134887578
725 2142794202
726 2158607450
727 2166579778
728 2182524434
729 2190562829
730 2206639619
731 2214744445
732 2230954097
733 2239125719
734 2255468963
735 2263707747
736 2280185315
737 2288491628
738 2305104254
739 2313478464
740 2330226884
741 2338669360
742 2355554312
743 2364065424
744 2381087648
745 2389667767
746 2406828005
747 2415477503
748 2432776499
749 2441495749
750 2458934249
751 2467723625
752 2485302377
753 2494162254
754 2511882008
755 2520812762
756 2538674270
757 2547676278
758 2565680294
759 2574753934
760 2592901214
761 2602046865
762 2620338167
763 2629556209
764 2647992293
765 2657283107
766 2675864735
767 2685228703
768 2703956639
769 2713394144
770 2732269154
771 2741780580
772 2760803432
773 2770389164
774 2789560628
775 2799221052
776 2818541900
777 2828277403
778 2847748409
779 2857559379
780 2877181319
781 2887068145
782 2906841797
783 2916804869
784 2936731013
785 2946770722
786 2966850140
787 2976966878
788 2997200354
789 3007394514
790 3027782834
791 3038054810
792 3058598762
793 3068948949
794 3089649323
795 3100078117
796 3120935705
797 3131443503
798 3152459099
799 3163046299
800 3184220699
801 3194887700
802 3216221702
803 3226968904
804 3248463308
805 3259291112
806 3280946720
807 3291855528
808 3313673144
809 3324663359
810 3346643789
811 3357715815
812 3379859867
813 3391014109
814 3413322593
815 3424559457
816 3447033185
817 3458353078
818 3480992864
819 3492396194
820 3515202854
821 3526690030
822 3549664382
823 3561235814
824 3584378678
825 3596034777
826 3619346975
827 3631088153
828 3654570509
829 3666397179
830 3690050519
831 3701963095
832 3725788247
833 3737787144
834 3761784938
835 3773870572
836 3798041840
837 3810214628
838 3834560204
839 3846820564
840 3871341284
841 3883689635
842 3908386337
843 3920823099
844 3945696623
845 3958222217
846 3983273405
847 3995888253
848 4021117949
849 4033822474
850 4059231524
851 4072026150
852 4097615402
853 4110500554
854 4136270858
855 4149246962
856 4175199170
857 4188266653
858 4214401619
859 4227560909
860 4253879489
861 4267131015
862 4293634067
863 4306978259
864 4333666643
865 4347103932
866 4373978510
867 4387509328
868 4414570964
869 4428195744
870 4455445304
871 4469164480
872 4496602832
873 4510416839
874 4538044853
875 4551954127
876 4579772675
877 4593777653
878 4621787609
879 4635888729
880 4664090969
881 4678288670
882 4706684072
883 4720978794
884 4749568238
885 4763960422
886 4792744790
887 4807234878
888 4836215054
889 4850803489
890 4879980359
891 4894667585
892 4924042037
893 4938828499
894 4968401423
895 4983287567
896 5013059855
897 5028046128
898 5058018674
899 5073105524
900 5103279224
901 5118467100
902 5148842852
903 5164132204
904 5194710908
905 5210102187
906 5240884745
907 5256378403
908 5287365719
909 5302962209
910 5334155189
911 5349854965
912 5381254517
913 5397058034
914 5428665068
915 5444572782
916 5476388210
917 5492400578
918 5524425314
919 5540542794
920 5572777754
921 5589000805
922 5621446907
923 5637775989
924 5670434153
925 5686869727
926 5719740875
927 5736283403
928 5769368459
929 5786018404
930 5819318294
931 5836076120
932 5869591772
933 5886457944
934 5920190288
935 5937165272
936 5971115240
937 5988199503
938 6022368029
939 6039562039
940 6073950059
941 6091254285
942 6125862737
943 6143277649
944 6178107473
945 6195633542
946 6230685680
947 6248323378
948 6283598774
949 6301348574
950 6336848174
951 6354710550
952 6390435302
953 6408410729
954 6444361583
955 6462450537
956 6498628445
957 6516831403
958 6553237319
959 6571554759
960 6608189639
961 6626622040
962 6663486842
963 6682034684
964 6719130368
965 6737794132
966 6775121660
967 6793901828
968 6831462164
969 6850359219
970 6888153329
971 6907167755
972 6945196607
973 6964328889
974 7002593453
975 7021844077
976 7060345325
977 7079714778
978 7118453684
979 7137942454
980 7176919994
981 7196528570
982 7235745722
983 7255474594
984 7294932338
985 7314781997
986 7354481315
987 7374452253
988 7414394129
989 7434486839
990 7474672259
991 7494887235
992 7535317187
993 7555654924
994 7596330398
995 7616791392
996 7657713380
997 7678298128
998 7719467624
999 7740176624
1000 7781594624