1 1
2 1
3 17
4 21
5 132
6 351
7 816
8 874
9 1104
10 4031
11 3286
12 8473
13 11726
14 11868
15 11233
16 24857
17 28143
18 38247
19 46766
20 40754
21 66722
22 65017
23 83249
24 120150
25 156364
26 173013
27 152955
28 184147
29 218763
30 245436
31 297053
32 327500
33 437030
34 413803
35 556217
36 488334
37 652335
38 701878
39 615896
40 868979
41 867792
42 1000749
43 915081
44 1226708
45 1283849
46 1125345
47 1487761
48 1661796
49 1807828
50 2025505
51 2144066
52 1832652
53 2386864
54 2399309
55 2874288
56 2565039
57 3270771
58 2894822
59 3580225
60 3762590
61 3637399
62 4220665
63 4657497
64 4070368
65 5211450
66 5348107
67 5852411
68 6504100
69 6632558
70 7159735
71 7435592
72 6454820
73 7598735
74 8734541
75 8821983
76 8080151
77 9890325
78 10524867
79 10913616
80 11619690
81 11426130
82 12568113
83 11346937
84 13765936
85 12607202
86 13950070
87 15310900
88 16184198
89 16444331
90 15738296
91 16156799
92 15391707
93 18360874
94 18583368
95 20272873
96 18490783
97 22132847
98 23889934
99 23090450
100 26642627
101 26754317
102 28983495
103 28236702
104 31118610
105 30131670
106 32510488
107 32418249
108 35155412
109 31245637
110 36770382
111 34787777
112 38710337
113 39617570
114 38475802
115 39185731
116 44467452
117 43584469
118 40221402
119 46696683
120 45201469
121 48549789
122 51559876
123 52005109
124 51819210
125 53676880
126 57795347
127 59922553
128 53807084
129 60472587
130 66124663
131 65762132
132 62427603
133 66223180
134 72872605
135 74293386
136 76903076
137 77402809
138 79537368
139 84841447
140 89279622
141 86435569
142 92803377
143 89689717
144 91703549
145 95715511
146 86641013
147 104162389
148 105947482
149 102872981
150 99116413
151 113233855
152 115217180
153 113379849
154 104705915
155 122917547
156 112938492
157 121124200
158 135050588
159 138820298
160 139643459
161 139080208
162 145696546
163 145328496
164 145276165
165 156976544
166 145023956
167 153613919
168 166268693
169 173507640
170 174131661
171 169339458
172 178686231
173 163784660
174 185983386
175 174252768
176 194348230
177 190451710
178 200211761
179 189175732
180 205058787
181 208448555
182 206017894
183 219112617
184 221982338
185 209358224
186 228570445
187 233822727
188 232573300
189 242913382
190 226651467
191 258401136
192 257100921
193 262478479
194 275979623
195 272048530
196 285472970
197 292318596
198 299415707
199 302964848
200 278330340
201 311024259
202 290065454
203 317410489
204 328606904
205 320318557
206 348711667
207 329485748
208 342523793
209 360345106
210 350697568
211 367715064
212 368912861
213 358945228
214 362291251
215 342878007
216 388667262
217 375811708
218 423946056
219 401923973
220 433438251
221 441915857
222 429442636
223 470544004
224 470627367
225 468525483
226 489582545
227 494416526
228 455731300
229 480354802
230 494944806
231 514407043
232 505384469
233 505076676
234 546290546
235 535343721
236 506542089
237 556290400
238 557135345
239 546208618
240 518458853
241 580075671
242 584623067
243 589061852
244 623433775
245 629008484
246 568935224
247 622261968
248 624620174
249 644295160
250 619163539
251 682715903
252 689595528
253 656157384
254 701694554
255 702395367
256 686962747
257 714421709
258 707886549
259 734228877
260 765537314
261 742324951
262 753310632
263 779391289
264 813064943
265 820594532
266 800791369
267 835870191
268 856490070
269 844356150
270 871208561
271 884711783
272 880250408
273 906339566
274 864537946
275 943963724
276 916902401
277 939116749
278 959975611
279 983738618
280 951392551
281 934132545
282 990402548
283 975947412
284 1080215589
285 1075044738
286 1011977125
287 1105654376
288 1106605997
289 1057132916
290 1132160816
291 1150262783
292 1131301052
293 1175328070
294 1159955562
295 1210141119
296 1239180047
297 1173957671
298 1285182605
299 1245754773
300 1292696499
301 1331112742
302 1332628055
303 1276389486
304 1320285462
305 1340289269
306 1380216964
307 1364440591
308 1399853767
309 1318280787
310 1449707473
311 1366520885
312 1482622641
313 1513577892
314 1490046971
315 1437700908
316 1533697842
317 1498339665
318 1457588503
319 1585967088
320 1620739572
321 1582216356
322 1641134794
323 1642444599
324 1609270849
325 1674840230
326 1697768040
327 1706525251
328 1768590430
329 1695461540
330 1813307857
331 1835867495
332 1873055759
333 1781746942
334 1841783375
335 1881968809
336 1912243971
337 1957554791
338 1969781800
339 1995989050
340 1916494565
341 2019374017
342 2033952154
343 2059731905
344 1978292263
345 2124464795
346 2079406085
347 2149377445
348 2139558058
349 1990253156
350 2190371885
351 2183539256
352 2257498702
353 2259128515
354 2171625517
355 2284517085
356 2298481286
357 2129904170
358 2267523801
359 2368950040
360 2272538969
361 2423657425
362 2440868186
363 2329756889
364 2419176495
365 2479574299
366 2542110458
367 2541736395
368 2546204283
369 2694227994
370 2646195934
371 2690885519
372 2626079810
373 2771367113
374 2631782517
375 2799769251
376 2787424464
377 2706011899
378 2928388992
379 2979791080
380 3010560162
381 3012165903
382 3061942030
383 3036781338
384 3145909256
385 3085588688
386 2993233304
387 3092099176
388 3211856569
389 3199128710
390 3047428806
391 3268812936
392 3266126953
393 3220400917
394 3278601999
395 3124159111
396 3354662482
397 3196839779
398 3409956454
399 3351911967
400 3445483597
401 3478625835
402 3499822828
403 3448520401
404 3590511042
405 3628882249
406 3469653978
407 3663630871
408 3687146768
409 3633119662
410 3648225764
411 3818011436
412 3819115497
413 3767188225
414 3815513257
415 3917181274
416 3917564439
417 3738868051
418 3904144953
419 4076009472
420 3826746212
421 4118617471
422 4153880925
423 4044493476
424 4103637530
425 4323587702
426 4323509539
427 4276284564
428 4390361246
429 4320003347
430 4164972213
431 4540567018
432 4452221172
433 4551864041
434 4387255716
435 4688128827
436 4716943756
437 4762641666
438 4803018161
439 4773009549
440 4668228929
441 4819771054
442 4944389316
443 5032006661
444 4718969025
445 5106392940
446 5175522984
447 5226553852
448 5025810477
449 5345811452
450 5388636267
451 5356954999
452 5061541863
453 5417717553
454 5540935374
455 5590206636
456 5590177561
457 5636978315
458 5560175547
459 5760363605
460 5791799334
461 5718567300
462 5685861544
463 5834410161
464 6022836249
465 5975749000
466 6104600060
467 5864975029
468 6018989776
469 6187186188
470 6073895295
471 6117736802
472 6184663581
473 5924453045
474 6377080736
475 6262313442
476 6420771967
477 6510780739
478 6283180509
479 6257490399
480 6647708293
481 6790467134
482 6878264822
483 6933455996
484 6932552589
485 6804670332
486 6828412515
487 6989198971
488 6947652051
489 7069313119
490 6957632837
491 7278371711
492 6905086533
493 7381178762
494 7371926003
495 7240217143
496 7430990337
497 7377830940
498 7524694777
499 7225172167
500 7490761715
501 7679665779
502 7477000817
503 7772744086
504 7694596680
505 7892927283
506 7929404420
507 7627375095
508 7691859566
509 8050648617
510 7994942372
511 7967143190
512 7696056937
513 8313460854
514 8311516539
515 8288753206
516 8480533512
517 8476744493
518 8539449531
519 8106096036
520 8409558076
521 8704672861
522 8631560019
523 8919181412
524 8628878550
525 8987172962
526 8769626759
527 9155573744
528 9150530789
529 9054923985
530 9328432739
531 9096824677
532 9436470366
533 9314995002
534 9329432600
535 9569199063
536 9148901283
537 9750007541
538 9797250734
539 9874482120
540 9882588499
541 9331786796
542 10047022743
543 9728368840
544 9881617239
545 10167128306
546 10035280867
547 10003359456
548 10111945604
549 10141242767
550 10611477965
551 10735867296
552 10582522944
553 10261153649
554 10804260095
555 10661904625
556 10879012529
557 10807098820
558 11124076836
559 10985530157
560 11203867998
561 11318826270
562 10599946377
563 11131021896
564 11470055387
565 11348216767
566 11245755608
567 11293721215
568 11813547964
569 11799950581
570 11650726235
571 12015683862
572 12006343011
573 11717466784
574 12222386532
575 12443471226
576 12236917551
577 12560545350
578 12378389897
579 12647048637
580 12162483372
581 12781797224
582 12645642022
583 12858209731
584 12553755997
585 12945280185
586 12387458915
587 13085139532
588 12897423598
589 13219178368
590 13304483122
591 13319804100
592 13666233960
593 13450266506
594 13753238459
595 13834246189
596 13751757152
597 13975815009
598 13343976758
599 14208953867
600 14360245270
601 14447001273
602 14093460469
603 14693963346
604 14484132479
605 14404539848
606 14826130274
607 14263212440
608 15078672544
609 14920562682
610 15158299187
611 15121372602
612 15412653184
613 15403299741
614 15079473695
615 15201649218
616 15487454854
617 15748442393
618 15920006304
619 15526662817
620 15397601343
621 15605970523
622 16245820985
623 16174974221
624 16510883831
625 16662424231
626 16084646974
627 16536360224
628 16835395806
629 16578973204
630 16939464940
631 16534172649
632 17091460116
633 16071316904
634 16968060032
635 16502027490
636 17625173676
637 17453156942
638 17743784938
639 17721066683
640 16840594142
641 17335219062
642 17968047384
643 17990474678
644 18376872801
645 18437223514
646 17689267568
647 18562471176
648 18648907035
649 18716723252
650 18400510871
651 19214828155
652 18176584632
653 19384997183
654 19575565778
655 19313662256
656 19792611827
657 18730155004
658 19551094485
659 20073940761
660 20153278330
661 19450902720
662 19840746322
663 20371678803
664 19689585360
665 20576340798
666 20551235799
667 20553122580
668 20870420448
669 20402253733
670 20676873685
671 21055551896
672 20701202672
673 21160678135
674 20800469035
675 20264550138
676 21101047498
677 21330034045
678 21884941585
679 21968607918
680 21040620485
681 21582001905
682 22200771139
683 22101854999
684 22407119166
685 21838984940
686 22467092495
687 22913432860
688 22544142867
689 22570148105
690 22997665419
691 23353473297
692 23471704815
693 23706315270
694 23589863933
695 22823323790
696 24022295820
697 24002789233
698 24341315967
699 24548904978
700 23299837836
701 24698075180
702 24877741884
703 24074612430
704 25007041099
705 24917681605
706 25343807913
707 25285834672
708 24197441391
709 26040300205
710 25713934097
711 26257977700
712 25070742410
713 25710317442
714 26523640457
715 26610286622
716 26323778758
717 25850576989
718 26874150399
719 26979111444
720 26735221322
721 27127683030
722 26222787492
723 27451583889
724 26759830488
725 27209782276
726 27820377831
727 27388458515
728 27478834107
729 26532642171
730 28216417624
731 27841709800
732 27841234301
733 28690396453
734 28453159545
735 28964591760
736 28922760973
737 29078276887
738 27573291248
739 29101853369
740 28493945946
741 30096438582
742 29669693761
743 29573361347
744 30206313689
745 30308045026
746 29891998095
747 30448136641
748 30404453493
749 30865726390
750 30831619951
751 30987996437
752 29258840773
753 31219239241
754 31647735962
755 31622800099
756 31082833157
757 31781213621
758 31941295828
759 31338961799
760 31805799271
761 32689273110
762 31532178403
763 32818320401
764 32989766591
765 32711781583
766 32539806921
767 32812009230
768 33510757586
769 33016034502
770 33667605676
771 33649577609
772 33288642226
773 33806467075
774 32111574199
775 34103154470
776 34323358766
777 33001506599
778 34500154171
779 33446049146
780 34287052617
781 35346794732
782 35752522023
783 35488714823
784 35629991884
785 35701547059
786 36626313667
787 36782867485
788 36606100972
789 35545402836
790 37052331801
791 36934251843
792 37536059130
793 36378371251
794 37793412226
795 37375441925
796 37952423589
797 38236448220
798 38441165410
799 37817828907
800 38569167469
801 37852803563
802 37661392008
803 38796029533
804 39297805667
805 39763849913
806 38943171830
807 39442346176
808 39634161135
809 40265357918
810 40228115163
811 40414082137
812 39782745112
813 40998767248
814 39424564131
815 41173682387
816 40089010502
817 41342487565
818 40399243506
819 40791675203
820 41838230435
821 40110841633
822 42113158563
823 41702815368
824 42448362498
825 42642306700
826 41859759509
827 42916014308
828 40804183199
829 43139067966
830 42258205589
831 43272115549
832 42905944996
833 43577637581
834 43758441811
835 44271003541
836 44049758220
837 44909314036
838 44379357754
839 45272940705
840 45388507702
841 45619525684
842 44917375977
843 46427994086
844 46642235824
845 46524441981
846 44335392679
847 47148559774
848 46608542419
849 47448110346
850 46952521965
851 47667202120
852 47631784113
853 45510036495
854 47075529093
855 48035287658
856 48876613531
857 49194005127
858 48691520283
859 49418711693
860 49784690568
861 48419397142
862 50107031440
863 49444161532
864 50278614851
865 49666602424
866 50488398357
867 48173436027
868 51023313635
869 51167299416
870 51729830810
871 51337283752
872 51013703645
873 52133270559
874 50318233677
875 52500012978
876 52023486617
877 52159126269
878 52624236404
879 53255239455
880 53387650264
881 53657780278
882 53955881610
883 51956073843
884 54157016285
885 52990010875
886 54122777282
887 53882866457
888 54500871504
889 52924189204
890 55290161041
891 55166127000
892 56099506317
893 53855617492
894 56519811656
895 55548943017
896 55353574050
897 56829534836
898 55349262121
899 55199202232
900 57266141845
901 57444395170
902 57613092405
903 56561888543
904 57546794341
905 57049842058
906 57643806779
907 58869945648
908 59056907219
909 56981794627
910 57772442281
911 60031786993
912 60449912644
913 58315893530
914 60706215310
915 58760446345
916 59472841257
917 61929342574
918 61213073278
919 62276720666
920 61623489535
921 61570582675
922 62717287455
923 62297898147
924 63114685727
925 63349752541
926 62975118174
927 62186883844
928 63740328649
929 63707969670
930 65074967068
931 64342110008
932 65287576719
933 65734980802
934 64765470246
935 65910213945
936 66311004417
937 65299454921
938 67037193110
939 67686700216
940 67138694630
941 68343991002
942 68705582694
943 67957925895
944 69377869868
945 68734483607
946 69866261889
947 70067928758
948 68111702223
949 70370897752
950 69342443108
951 70185517901
952 70946791543
953 69956790765
954 71437455874
955 71695079392
956 71649039365
957 71201258313
958 71920734663
959 68685216332
960 72429102422
961 72588575713
962 72770099006
963 70847119704
964 73024370833
965 71015892525
966 72916959253
967 70775489965
968 73995131633
969 73375696434
970 73549918882
971 74893470124
972 75408149657
973 75582564234
974 75929050748
975 74832522215
976 74535795991
977 75244167061
978 73759853113
979 76800702965
980 76489395192
981 74459017851
982 77536263451
983 78053560090
984 77965754383
985 76361323555
986 78990764847
987 79181524628
988 79901574938
989 77483451110
990 80165397805
991 80682447256
992 80888750639
993 80791832171
994 81707726060
995 81641079853
996 79983156365
997 81100083276
998 82399742327
999 81719698956
1000 79710349571