1 0
2 2
3 7
4 12
5 24
6 31
7 59
8 74
9 111
10 121
11 202
12 208
13 323
14 310
15 454
16 484
17 695
18 597
19 957
20 874
21 1183
22 1125
23 1665
24 1448
25 2070
26 1823
27 2439
28 2304
29 3273
30 2524
31 3980
32 3464
33 4367
34 3982
35 5470
36 4440
37 6692
38 5515
39 7110
40 6488
41 9056
42 6728
43 10422
44 8592
45 10542
46 9666
47 13554
48 10384
49 15110
50 12005
51 15622
52 14026
53 19338
54 14103
55 20806
56 17488
57 21679
58 19147
59 26572
60 19096
61 29333
62 23320
63 28749
64 26128
65 34143
66 25356
67 38751
68 30922
69 38111
70 31928
71 46035
72 33720
73 49996
74 39377
75 47270
76 42960
77 57315
78 41508
79 63230
80 48976
81 61263
82 53392
83 73237
84 51776
85 75759
86 61501
87 75718
88 66552
89 90146
90 61572
91 94306
92 75648
93 92287
94 80100
95 105478
96 78368
97 116485
98 89194
99 110517
100 93770
101 131388
102 91816
103 139295
104 109224
105 126028
106 114493
107 156046
108 109872
109 164903
110 122772
111 156102
112 134432
113 183611
114 127700
115 186334
116 150538
117 181854
118 157545
119 209957
120 146912
121 223652
122 173987
123 211846
124 183552
125 239100
126 169368
127 260144
128 202784
129 244111
130 202032
131 285367
132 198048
133 292647
134 230095
135 269766
136 242384
137 326180
138 225240
139 340602
140 250352
141 318143
142 273510
143 366414
144 259248
145 371967
146 297128
147 354025
148 310762
149 419118
150 279020
151 436145
152 337480
153 404886
154 340056
155 453886
156 325464
157 489977
158 376060
159 455110
160 380192
161 517834
162 363069
163 548067
164 421930
165 487124
166 435771
167 589239
168 403264
169 607529
170 449836
171 564357
172 486288
173 654783
174 448948
175 640550
176 519600
177 626639
178 536692
179 725017
180 482808
181 749498
182 560584
183 692166
184 596208
185 769839
186 547616
187 818002
188 633984
189 748503
190 627020
191 880200
192 608320
193 908041
194 693962
195 802668
196 705264
197 965472
198 655812
199 995075
200 738040
201 915823
202 782977
203 1035370
204 723448
205 1046175
206 830206
207 998637
208 856176
209 1141215
210 745952
211 1185477
212 907306
213 1088927
214 930285
215 1206214
216 863208
217 1263886
218 983207
219 1183110
220 970248
221 1350603
222 927996
223 1398740
224 1053760
225 1235310
226 1094998
227 1475131
228 1007840
229 1514348
230 1109544
231 1352814
232 1190216
233 1594856
234 1081116
235 1573630
236 1249680
237 1497919
238 1250960
239 1720890
240 1140544
241 1764331
242 1333695
243 1614087
244 1380490
245 1749370
246 1260544
247 1884694
248 1452352
249 1736111
250 1425025
251 1992532
252 1336704
253 2022067
254 1552480
255 1790164
256 1597504
257 2138465
258 1453100
259 2145646
260 1599828
261 1996734
262 1703295
263 2291355
264 1558752
265 2253903
266 1745000
267 2138758
268 1827024
269 2451363
270 1603836
271 2506310
272 1909504
273 2232132
274 1947352
275 2499830
276 1781952
277 2676062
278 2033605
279 2437437
280 1975744
281 2793386
282 1895088
283 2853312
284 2172672
285 2496676
286 2186220
287 2917169
288 2032224
289 3028967
290 2218528
291 2766342
292 2360746
293 3165828
294 2107448
295 3106438
296 2463384
297 2919015
298 2503237
299 3340530
300 2205080
301 3364083
302 2605090
303 3121606
304 2663120
305 3432255
306 2412552
307 3640521
308 2698176
309 3310111
310 2708192
311 3784365
312 2568480
313 3857686
314 2927147
315 3311364
316 2989440
317 4007157
318 2713228
319 4048222
320 2995264
321 3709583
322 3091248
323 4215262
324 2878200
325 4129215
326 3274711
327 3920838
328 3347648
329 4390294
330 2898768
331 4560642
332 3465168
333 4137966
334 3521070
335 4544710
336 3161216
337 4812655
338 3629483
339 4367110
340 3571084
341 4943259
342 3365340
343 4974995
344 3859768
345 4421612
346 3913303
347 5253016
348 3560152
349 5344193
350 3822040
351 4820742
352 4105824
353 5529701
354 3738300
355 5406046
356 4269418
357 4986688
358 4333635
359 5815935
360 3810336
361 5898873
362 4480157
363 5318797
364 4454000
365 5874783
366 4130004
367 6212714
368 4716384
369 5625894
370 4597656
371 6290806
372 4345088
373 6521858
374 4887480
375 5681350
376 5035488
377 6689991
378 4463496
379 6841092
380 4981880
381 6193663
382 5262480
383 7059600
384 4792448
385 6708348
386 5429138
387 6487797
388 5523082
389 7396008
390 4783008
391 7474493
392 5597872
393 6795887
394 5772937
395 7441918
396 5203584
397 7860947
398 5950150
399 6958694
400 5832080
401 8100551
402 5467268
403 8169754
404 6232810
405 7151598
406 6187496
407 8398182
408 5728448
409 8594266
410 6250900
411 7770502
412 6609408
413 8673147
414 5961672
415 8627974
416 6779232
417 8114959
418 6821820
419 9239107
420 5907008
421 9371828
422 7090075
423 8466909
424 7212344
425 9237495
426 6502536
427 9583738
428 7407504
429 8720844
430 7208564
431 10054530
432 6811920
433 10194931
434 7555136
435 8848012
436 7829578
437 10435719
438 7065888
439 10623965
440 7698336
441 9409323
442 8075388
443 10916572
444 7373208
445 10633407
446 8367016
447 9990598
448 8343680
449 11365481
450 7371060
451 11422186
452 8721226
453 10397407
454 8824455
455 11083920
456 7989280
457 11982940
458 9059297
459 10782054
460 8826576
461 12299883
462 8072160
463 12460430
464 9437872
465 10803004
466 9541408
467 12785701
468 8589816
469 12693183
470 9407568
471 11683782
472 9940440
473 13174167
474 8949200
475 12896390
476 9956144
477 12132174
478 10296180
479 13795380
480 8985728
481 13882303
482 10556342
483 12334050
484 10621512
485 13760079
486 9644751
487 14497199
488 10983048
489 13072111
490 10454696
491 14856862
492 10022200
493 14975043
494 11273140
495 12937452
496 11523200
497 15101026
498 10374420
499 15593937
500 11343850
501 14056223
502 11923065
503 15971445
504 10596288
505 15530415
506 12095496
507 14487174
508 12370944
509 16549053
510 10685584
511 16411457
512 12681344
513 15051591
514 12797122
515 16469854
516 11556512
517 17197675
518 12834040
519 15623110
520 12710976
521 17745716
522 11933004
523 17950602
524 13574352
525 15246140
526 13712886
527 18289193
528 12317376
529 18542704
530 13480072
531 16726677
532 13896000
533 18882771
534 12784048
535 18460870
536 14542888
537 17302319
538 14671327
539 19106661
540 12743064
541 19865993
542 15000460
543 17887686
544 15158144
545 19513887
546 13331232
547 20533491
548 15521962
549 18482814
550 14949060
551 20910646
552 14149056
553 20792998
554 16017317
555 18348444
556 16210320
557 21678927
558 14570592
559 21779950
560 15644288
561 19509512
562 16720132
563 22386217
564 15079296
565 21738543
566 17079121
567 19963125
568 17299152
569 23108726
570 14911280
571 23352972
572 17417544
573 21013247
574 17454272
575 22873670
576 16091328
577 24096025
578 18129038
579 21679110
580 17669812
581 24109383
582 16540536
583 24650614
584 18799104
585 21376044
586 18951313
587 25369186
588 16760576
589 25539255
590 18585060
591 23052742
592 19571664
593 26154191
594 17449452
595 24804520
596 19958698
597 23760799
598 19992408
599 26955225
600 17496160
601 27225826
602 20130968
603 24479589
604 20771712
605 26473766
606 18667324
607 28048484
608 21158560
609 24701236
610 20536320
611 28433706
612 19201080
613 28887548
614 21795235
615 24951940
616 21466560
617 29456120
618 19795880
619 29743182
620 21576128
621 26693271
622 22657050
623 29717321
624 20337600
625 29414250
626 23096348
627 27237090
628 23342602
629 31084767
630 19777056
631 31504805
632 23813920
633 28315567
634 23991907
635 30845950
636 21602584
637 31587766
638 24231324
639 29123277
640 23777408
641 33024881
642 22187628
643 33334647
644 24637056
645 28777492
646 25232840
647 33959979
648 22884984
649 33994855
650 24706560
651 30164954
652 26117328
653 34912563
654 23452548
655 33849286
656 26615392
657 31650534
658 26277984
659 35882797
660 23047392
661 36210158
662 27308245
663 32245860
664 27609288
665 34633388
666 24751332
667 37098778
668 28084224
669 33418111
670 27199388
671 37566846
672 25030912
673 38216221
674 28818302
675 32987430
676 28943434
677 38901012
678 26124808
679 38461517
680 28421408
681 35246063
682 29593440
683 39943462
684 26799360
685 38710239
686 29782102
687 36184518
688 30695984
689 40759407
690 26429856
691 41362137
692 31215946
693 36124938
694 31457025
695 40428358
696 28313504
697 42286534
698 32003387
699 38111110
700 30450160
701 43182213
702 28835460
703 43410502
704 32643264
705 37562588
706 33115018
707 43412878
708 29778720
709 44676128
710 32359032
711 40100637
712 34026656
713 45312838
714 29816768
715 43423572
716 34572240
717 41127359
718 34830270
719 46591470
720 30171072
721 46040434
722 35323945
723 42167046
724 35742250
725 45838335
726 31816356
727 48162569
728 35468352
729 43224111
730 35167092
731 48776962
732 32903640
733 49363793
734 37208020
735 41736436
736 37518528
737 49765455
738 33661776
739 50584827
740 36654564
741 45023388
742 37664024
743 51409935
744 34569472
745 49784847
746 39060653
747 46496517
748 38978472
749 51609363
750 33975100
751 53086970
752 40066752
753 47629007
754 40060104
755 51814366
756 35544384
757 54368402
758 40973785
759 48309086
760 39672160
761 55234046
762 37063808
763 54554770
764 41989632
765 47837172
766 42283296
767 56213694
768 38043904
769 56992801
770 40138656
771 51122182
772 43320586
773 57886008
774 38823972
775 55986230
776 44031984
777 51257388
778 44299417
779 59056270
780 38067312
781 59212579
782 44761776
783 53486982
784 44518880
785 58232319
786 40670916
787 61085661
788 46066282
789 54782111
790 44556080
791 60777557
792 41399712
793 62121511
794 47085887
795 53834428
796 47481600
797 63441897
798 41623840
799 63683777
800 46368160
801 57311814
802 48521902
803 64354314
804 43573856
805 61437828
806 48927520
807 58612678
808 49697048
809 66348416
810 42777828
811 66841302
812 49353584
813 59928127
814 50295540
815 65159494
816 45474304
817 68121759
818 51480932
819 59715180
820 49852060
821 69342378
822 46508896
823 69849965
824 52703248
825 59697220
826 51939000
827 70872556
828 47514240
829 71387573
830 51662604
831 63992262
832 53953728
833 70741973
834 48572300
835 70070110
836 54423840
837 65326455
838 55345815
839 74000115
840 46932736
841 74447727
842 56141297
843 66801286
844 56586192
845 72204639
846 50678928
847 74014545
848 57423376
849 68236111
850 55309580
851 77029422
852 51835968
853 77763638
854 57395752
855 66792828
856 59074488
857 78861890
858 52180272
859 79414872
860 57498056
861 69720616
862 60233220
863 80528580
864 54121248
865 77889183
866 61074758
867 72427718
868 60274176
869 81547275
870 52930912
871 82297606
872 62444136
873 74175606
874 62508600
875 79012750
876 56332344
877 84508487
878 63646330
879 75719110
880 61205952
881 85669211
882 56307048
883 86253537
884 64435836
885 74234036
886 65400201
887 87430149
888 58714848
889 86254654
890 63679588
891 78233661
892 66786048
893 88943127
894 59808748
895 86269318
896 66404608
897 79869156
898 68090962
899 90835282
900 58725240
901 91299543
902 68418624
903 80417870
904 69563024
905 89190735
906 62245976
907 93473946
908 70440144
909 83724654
910 66350016
911 94715190
912 63475520
913 94561567
914 71792072
915 82031820
916 72316138
917 94656735
918 64542888
919 97230545
920 70347072
921 87086383
922 73691887
923 97923234
924 64310784
925 95168895
926 74654236
927 88792077
928 75168224
929 100436861
930 64638848
931 98798049
932 76167466
933 90531167
934 76603995
935 97243996
936 68403168
937 103052080
938 76030664
939 92287110
940 75057312
941 104376543
942 69953076
943 104797817
944 79182960
945 88588332
946 78919236
947 106384441
948 71365760
949 106427827
950 77235100
951 95866822
952 79374208
953 108417926
954 72637716
955 104790526
956 82197120
957 96810428
958 82656360
959 108256097
960 71332096
961 111061205
962 83165008
963 99532149
964 84275530
965 108114063
966 73818048
967 113263139
968 84715752
969 100815064
970 82417116
971 114673522
972 76921488
973 113062947
974 86863390
975 98689740
976 87500592
977 116810975
978 78271460
979 116569882
980 83390384
981 105212574
982 89019405
983 118974825
984 79846016
985 114970479
986 89716252
987 104985546
988 89977400
989 120887811
990 77410224
991 121901300
992 91803904
993 109123087
994 90462096
995 118504798
996 82744032
997 124127372
998 93437875
999 111039174