4 1
5 4
6 14
7 29
8 56
9 100
10 148
11 230
12 322
13 446
14 573
15 778
16 953
17 1215
18 1456
19 1806
20 2134
21 2542
22 2944
23 3477
24 3968
25 4600
26 5186
27 5872
28 6657
29 7446
30 8304
31 9217
32 10258
33 11172
34 12465
35 13564
36 14867
37 16072
38 17716
39 18816
40 20832
41 22055
42 24144
43 25504
44 27904
45 29168
46 32051
47 33375
48 36344
49 37853
50 41310
51 42438
52 46428
53 47772
54 52018
55 53300
56 58045
57 59046
58 64512
59 65500
60 71102
61 72238
62 78617
63 79301
64 86225
65 86798
66 94474
67 94820
68 102959
69 103202
70 112338
71 112055
72 121798
73 121375
74 131956
75 131090
76 142368
77 141474
78 153880
79 152077
80 165046
81 163578
82 177549
83 174904
84 190350
85 187004
86 203498
87 200326
88 217174
89 213057
90 232198
91 226856
92 246277
93 241842
94 262219
95 255608
96 279010
97 271305
98 295077
99 288380
100 311839
101 303576
102 331560
103 320609
104 348654
105 339520
106 368134
107 356348
108 389456
109 375214
110 408148
111 396600
112 429301
113 414407
114 453454
115 434632
116 473440
117 459198
118 496852
119 477804
120 523108
121 500504
122 545008
123 526774
124 570089
125 546548
126 599851
127 571367
128 622596
129 600646
130 649682
131 621802
132 682604
133 648070
134 706560
135 679912
136 736235
137 702625
138 771714
139 730888
140 796888
141 766314
142 828993
143 789526
144 868373
145 819218
146 894457
147 858054
148 928954
149 882404
150 970690
151 914933
152 999290
153 957075
154 1035066
155 981022
156 1082308
157 1016518
158 1109929
159 1061930
160 1149216
161 1087364
162 1198988
163 1124406
164 1229603
165 1173728
166 1269786
167 1199997
168 1325060
169 1239326
170 1354036
171 1292582
172 1399690
173 1319182
174 1456608
175 1359661
176 1489874
177 1418522
178 1534125
179 1445194
180 1599234
181 1489196
182 1628710
183 1551028
184 1679831
185 1577998
186 1745628
187 1624808
188 1780443
189 1690792
190 1829112
191 1718561
192 1905242
193 1767241
194 1934603
195 1838656
196 1991910
197 1866136
198 2066934
199 1916825
200 2102902
201 1993836
202 2156578
203 2020050
204 2244422
205 2074424
206 2272927
207 2156155
208 2337028
209 2183398
210 2421080
211 2239098
212 2459402
213 2326646
214 2516682
215 2352910
216 2617042
217 2411134
218 2644324
219 2504744
220 2716224
221 2531176
222 2810684
223 2591581
224 2848465
225 2691408
226 2911287
227 2715852
228 3026042
229 2779796
230 3050650
231 2884420
232 3128784
233 2909327
234 3235590
235 2976416
236 3274938
237 3087874
238 3340072
239 3110311
240 3471510
241 3180057
242 3491654
243 3297672
244 3578280
245 3320190
246 3696990
247 3392494
248 3735517
249 3517628
250 3807240
251 3537652
252 3952237
253 3612634
254 3969181
255 3746824
256 4064093
257 3763723
258 4195712
259 3839778
260 4236890
261 3981198
262 4308590
263 3997705
264 4472682
265 4080710
266 4483688
267 4226316
268 4588362
269 4240962
270 4735356
271 4324123
272 4770909
273 4479432
274 4848659
275 4494818
276 5033442
277 4578864
278 5036942
279 4741769
280 5151730
281 4753035
282 5310550
283 4841684
284 5346715
285 5018520
286 5428120
287 5020084
288 5632030
289 5114079
290 5632600
291 5295160
292 5752551
293 5299376
294 5926490
295 5398480
296 5961112
297 5584772
298 6046334
299 5586262
300 6279040
301 5683490
302 6261417
303 5884234
304 6393882
305 5887370
306 6585619
307 5983296
308 6616490
309 6193178
310 6710130
311 6187091
312 6956488
313 6291579
314 6933528
315 6515400
316 7078217
317 6502014
318 7286172
319 6608338
320 7319866
321 6839438
322 7404690
323 6825240
324 7682347
325 6942956
326 7647786
327 7175800
328 7801487
329 7156676
330 8036876
331 7271802
332 8054354
333 7522412
334 8147131
335 7508230
336 8451270
337 7618067
338 8404092
339 7879708
340 8579520
341 7852222
342 8815792
343 7970950
344 8834724
345 8257392
346 8932256
347 8213910
348 9266002
349 8337454
350 9211383
351 8622504
352 9381316
353 8585705
354 9647644
355 8722634
356 9662613
357 9010392
358 9760036
359 8966083
360 10134226
361 9097416
362 10045924
363 9406244
364 10236984
365 9369936
366 10524432
367 9490527
368 10531565
369 9813103
370 10644546
371 9757714
372 11030782
373 9895668
374 10932906
375 10246036
376 11136667
377 10169846
378 11445100
379 10309156
380 11462756
381 10660242
382 11549647
383 10589601
384 11980424
385 10748456
386 11865511
387 11096796
388 12084329
389 11021932
390 12431212
391 11169348
392 12407669
393 11547418
394 12512236
395 11480302
396 12979662
397 11614042
398 12842817
399 12005880
400 13093347
401 11915773
402 13432276
403 12068104
404 13417202
405 12494732
406 13521046
407 12376096
408 14027236
409 12534713
410 13886854
411 12957302
412 14116369
413 12849742
414 14495305
415 13032010
416 14472142
417 13449980
418 14576336
419 13332122
420 15146364
421 13497892
422 14939254
423 13949181
424 15200998
425 13851567
426 15609630
427 13994696
428 15575742
429 14464452
430 15703420
431 14330963
432 16267812
433 14503143
434 16058554
435 15016504
436 16339104
437 14847346
438 16771498
439 15020065
440 16751000
441 15525485
442 16832558
443 15371732
444 17465436
445 15579880
446 17225731
447 16072294
448 17521845
449 15908941
450 18012216
451 16090304
452 17928675
453 16631078
454 18031166
455 16487692
456 18712162
457 16643797
458 18442140
459 17198758
460 18788088
461 17015798
462 19248344
463 17204591
464 19177408
465 17816320
466 19281169
467 17584230
468 20007968
469 17779862
470 19742174
471 18374144
472 20039554
473 18164952
474 20562000
475 18400762
476 20482096
477 18976508
478 20580409
479 18757039
480 21397388
481 18959222
482 21024707
483 19595424
484 21373767
485 19401792
486 21927374
487 19565523
488 21829524
489 20220602
490 21972408
491 19975756
492 22764474
493 20185128
494 22391276
495 20898120
496 22760945
497 20605226
498 23347818
499 20813854
500 23278744
501 21511054
502 23331234
503 21237711
504 24220659
505 21503286
506 23809796
507 22171924
508 24199083
509 21887314
510 24866336
511 22110806
512 24689826
513 22846604
514 24783813
515 22598364
516 25730506
517 22771374
518 25282190
519 23532878
520 25739874
521 23221587
522 26344814
523 23447782
524 26197960
525 24291742
526 26289655
527 23903904
528 27293480
529 24136199
530 26855670
531 24939990
532 27239126
533 24598580
534 27925344
535 24892758
536 27759614
537 25665842
538 27846216
539 25308246
540 28973332
541 25547902
542 28378355
543 26399532
544 28830577
545 26088422
546 29565564
547 26269174
548 29374761
549 27145082
550 29518540
551 26757022
552 30592382
553 27010596
554 30006434
555 27973440
556 30482422
557 27499590
558 31248115
559 27748408
560 31117680
561 28678866
562 31123751
563 28253328
564 32323026
565 28581336
566 31689396
567 29468709
568 32188645
569 29021969
570 33068864
571 29281266
572 32766698
573 30260374
574 32847570
575 29875957
576 34112847
577 30065225
578 33426905
579 31068208
580 34026190
581 30599330
582 34800022
583 30855872
584 34549067
585 31970062
586 34616464
587 31394400
588 35967204
589 31668518
590 35299784
591 32726662
592 35768178
593 32210333
594 36656582
595 32581524
596 36385770
597 33575682
598 36444230
599 33036203
600 37950764
601 33319679
602 37076158
603 34432368
604 37640197
605 33967988
606 38577440
607 34162645
608 38278120
609 35319852
610 38421376
611 34730496
612 39825071
613 35021048
614 38970164
615 36288956
616 39581074
617 35598605
618 40552652
619 35888984
620 40323634
621 37093352
622 40272261
623 36485224
624 41848388
625 36876428
626 40932251
627 38002996
628 41556252
629 37364480
630 42698790
631 37666809
632 42236261
633 38931082
634 42270234
635 38374916
636 43928822
637 38586080
638 42947004
639 39866613
640 43714964
641 39186397
642 44680444
643 39493616
644 44310216
645 40934372
646 44327304
647 40111539
648 46072136
649 40424102
650 45137688
651 41801480
652 45706992
653 41054618
654 46830944
655 41491796
656 46422157
657 42763039
658 46453304
659 42007492
660 48391252
661 42333168
662 47157260
663 43750948
664 47870988
665 43120208
666 49045644
667 43304574
668 48600885
669 44758986
670 48737860
671 43951046
672 50557072
673 44288199
674 49348177
675 45909968
676 50088445
677 44948944
678 51316900
679 45300804
680 50981856
681 46811236
682 50840568
683 45953080
684 52857536
685 46435764
686 51616312
687 47853836
688 52374624
689 46971614
690 53794208
691 47317896
692 53143376
693 48931186
694 53131460
695 48153456
696 55252572
697 48357182
698 53906512
699 49984048
700 54879905
701 49052906
702 56047696
703 49403894
704 55506860
705 51226140
706 55481067
707 50131276
708 57692886
709 50468264
710 56432274
711 52171333
712 57118999
713 51184418
714 58527912
715 51701396
716 57927112
717 53286782
718 57888389
719 52264869
720 60375842
721 52661482
722 58708088
723 54413122
724 59573942
725 53537588
726 61023530
727 53735889
728 60436986
729 55556324
730 60532376
731 54477942
732 62781072
733 54854138
734 61194251
735 56912674
736 62107695
737 55601676
738 63609783
739 55983142
740 63133346
741 57878168
742 62916086
743 56741203
744 65429140
745 57315686
746 63747508
747 59062960
748 64680512
749 57924230
750 66444596
751 58285899
752 65568367
753 60261006
754 65478912
755 59254830
756 68153880
757 59457600
758 66358706
759 61467652
760 67540192
761 60242491
762 68966564
763 60670114
764 68226841
765 62901840
766 68135207
767 61431262
768 70899264
769 61839075
770 69267932
771 63939232
772 70044113
773 62642984
774 71741484
775 63263019
776 70971981
777 65228432
778 70850710
779 63861682
780 73935232
781 64273482
782 71770640
783 66461780
784 72860018
785 65322490
786 74581418
787 65515342
788 73753134
789 67741714
790 73852506
791 66381728
792 76637660
793 66768214
794 74569692
795 69270256
796 75654525
797 67609862
798 77518704
799 68032724
800 76862392
801 70357991
802 76471827
803 68880918
804 79585856
805 69601400
806 77430170
807 71678998
808 78567850
809 70176933
810 80699588
811 70612844
812 79576550
813 73020558
814 79372368
815 71730282
816 82633158
817 71922686
818 80355761
819 74417128
820 81776556
821 72802588
822 83489262
823 73243539
824 82536451
825 76004076
826 82385356
827 74132536
828 85721663
829 74583714
830 83612432
831 77129728
832 84565136
833 75525121
834 86590924
835 76206416
836 85573230
837 78537032
838 85373974
839 76837487
840 89222548
841 77304574
842 86402436
843 79942218
844 87644772
845 78493962
846 89762989
847 78725275
848 88709470
849 81374862
850 88761761
851 79607276
852 92115350
853 80074752
854 89565194
855 83112660
856 90829268
857 81012357
858 92990572
859 81482282
860 92174354
861 84330440
862 91635745
863 82426191
864 95443630
865 83213794
866 92703865
867 85747002
868 94085722
869 83857178
870 96608000
871 84340210
872 95147016
873 87245705
874 94862388
875 85682208
876 98788280
877 85799222
878 95949611
879 88738746
880 97667028
881 86771721
882 99731791
883 87263448
884 98437336
885 90587716
886 98155800
887 88243237
888 102250236
889 88804362
890 99602478
891 91802816
892 100690145
893 89737538
894 103106880
895 90578964
896 101905045
897 93343792
898 101512947
899 91240796
900 106089289
901 91750328
902 102646702
903 94970024
904 104141105
905 93117130
906 106618456
907 93273566
908 105269350
909 96494228
910 105358144
911 94296389
912 109342058
913 94814672
914 106095603
915 98444036
916 107610930
917 95914930
918 110202022
919 96367941
920 109191878
921 99695416
922 108432228
923 97402836
924 113027128
925 98321030
926 109611237
927 101326825
928 111200196
929 98989277
930 114226500
931 99593836
932 112375251
933 102959194
934 111987228
935 100967748
936 116720198
937 101124201
938 113261926
939 104614516
940 115204780
941 102194046
942 117558572
943 102731976
944 116054896
945 106779496
946 115617708
947 103816512
948 120470858
949 104359304
950 117255328
951 107972798
952 118610328
953 105455941
954 121356308
955 106425982
956 119751835
957 109676472
958 119309759
959 107183894
960 124793270
961 107670591
962 120557254
963 111406394
964 122268921
965 109209948
966 125282544
967 109338055
968 123574796
969 113126294
970 123517760
971 110458064
972 128281386
973 111113346
974 124343931
975 115319096
976 126143824
977 112160475
978 129129318
979 112726846
980 127945356
981 116662074
982 126908656
983 113871251
984 132310778
985 114915306
986 128197848
987 118514576
988 130009362
989 115601390
990 133613948
991 116184813
992 131371957
993 120222922
994 130894484
995 117821406
996 136351904
997 117934480
998 132118732
999 122047544
1000 134523132