1 0
2 0
3 0
4 0
5 1
6 2
7 7
8 10
9 22
10 29
11 51
12 61
13 99
14 115
15 163
16 192
17 262
18 287
19 385
20 428
21 528
22 600
23 730
24 780
25 963
26 1054
27 1202
28 1337
29 1545
30 1646
31 1908
32 2059
33 2269
34 2516
35 2770
36 2933
37 3298
38 3568
39 3792
40 4142
41 4493
42 4786
43 5183
44 5562
45 5831
46 6423
47 6745
48 7140
49 7639
50 8231
51 8479
52 9216
53 9603
54 10260
55 10663
56 11488
57 11752
58 12838
59 13100
60 13887
61 14438
62 15609
63 15688
64 17012
65 17248
66 18576
67 18877
68 20286
69 20381
70 22122
71 22238
72 23779
73 24077
74 26061
75 25743
76 27974
77 27948
78 30128
79 30051
80 32273
81 32138
82 34947
83 34492
84 37028
85 36761
86 39996
87 39255
88 42456
89 41894
90 45177
91 44543
92 48158
93 47304
94 51383
95 50003
96 54145
97 53185
98 57686
99 56252
100 60672
101 59426
102 64510
103 62703
104 67859
105 65925
106 71874
107 69590
108 75404
109 73230
110 79400
111 77124
112 83328
113 80780
114 87988
115 84478
116 91950
117 89085
118 96666
119 92837
120 100815
121 97335
122 105973
123 102121
124 110498
125 105924
126 115911
127 110905
128 120506
129 116260
130 125787
131 120541
132 131635
133 125469
134 136974
135 131119
136 142286
137 136026
138 148998
139 141408
140 153508
141 147925
142 160413
143 152551
144 166969
145 158046
146 172980
147 165292
148 179211
149 170329
150 186660
151 176526
152 192510
153 184205
154 199588
155 188839
156 207960
157 195905
158 214117
159 204241
160 220706
161 209172
162 230496
163 216423
164 236561
165 225117
166 244584
167 230734
168 253770
169 238252
170 260228
171 248029
172 268966
173 253417
174 279602
175 260488
176 285840
177 272031
178 294888
179 277281
180 305626
181 285679
182 312646
183 297150
184 322036
185 302091
186 334560
187 311249
188 341295
189 323181
190 350434
191 329109
192 364121
193 338342
194 370985
195 351115
196 381091
197 357030
198 395248
199 366631
200 401674
201 381002
202 413117
203 385788
204 428589
205 395911
206 435115
207 411435
208 446453
209 416851
210 461628
211 427558
212 470028
213 443873
214 481288
215 448412
216 498630
217 459605
218 505457
219 477446
220 517741
221 482490
222 536324
223 493950
224 542820
225 511912
226 555970
227 517397
228 576402
229 529438
230 581516
231 548515
232 596183
233 553853
234 616262
235 565890
236 624091
237 587348
238 636362
239 591592
240 659324
241 604796
242 665431
243 626620
244 681369
245 630071
246 703720
247 644580
248 710586
249 668219
250 724147
251 671920
252 750286
253 685926
254 755579
255 710666
256 772508
257 714453
258 797694
259 728248
260 804410
261 755090
262 819480
263 758341
264 848538
265 773313
266 851842
267 801427
268 871576
269 803931
270 897938
271 819564
272 905470
273 848267
274 921133
275 850725
276 954733
277 867357
278 956510
279 897740
280 975413
281 900028
282 1007536
283 916564
284 1014132
285 949148
286 1029586
287 949385
288 1066254
289 967644
290 1067503
291 1001926
292 1090469
293 1002257
294 1122512
295 1020071
296 1129036
297 1055433
298 1146083
299 1055741
300 1187514
301 1073588
302 1186483
303 1112203
304 1210120
305 1111499
306 1246492
307 1130192
308 1251480
309 1170030
310 1269540
311 1168246
312 1315158
313 1187820
314 1312564
315 1228201
316 1339151
317 1227092
318 1378382
319 1246613
320 1382477
321 1290845
322 1399918
323 1287413
324 1451422
325 1308539
326 1446408
327 1353752
328 1474001
329 1348635
330 1517418
331 1370902
332 1521977
333 1417914
334 1539769
335 1414064
336 1594237
337 1435439
338 1587723
339 1485177
340 1618887
341 1478734
342 1664424
343 1500478
344 1667422
345 1554732
346 1686770
347 1546491
348 1748451
349 1569473
350 1736573
351 1622987
352 1769086
353 1615875
354 1820710
355 1640475
356 1822798
357 1695165
358 1841386
359 1686552
360 1907887
361 1711155
362 1894941
363 1769603
364 1928897
365 1761049
366 1984680
367 1784337
368 1984271
369 1845144
370 2005280
371 1833102
372 2078482
373 1859694
374 2059882
375 1925322
376 2097390
377 1910424
378 2154708
379 1936678
380 2157633
381 2003642
382 2175699
383 1988749
384 2254902
385 2016055
386 2234658
387 2084165
388 2275023
389 2069140
390 2338686
391 2096388
392 2333381
393 2168751
394 2355185
395 2153417
396 2441063
397 2179189
398 2416867
399 2252899
400 2460643
401 2235304
402 2527628
403 2263238
404 2523603
405 2343031
406 2541934
407 2320262
408 2636824
409 2350358
410 2609827
411 2431009
412 2653873
413 2407593
414 2724751
415 2441626
416 2718652
417 2522452
418 2739094
419 2498187
420 2843251
421 2529109
422 2807544
423 2614494
424 2855145
425 2593508
426 2933550
427 2620045
428 2925705
429 2709919
430 2947886
431 2683471
432 3053241
433 2715520
434 3014288
435 2812374
436 3067853
437 2779164
438 3149826
439 2811246
440 3140992
441 2905989
442 3159099
443 2876627
444 3278562
445 2914253
446 3232799
447 3009391
448 3284988
449 2976096
450 3377750
451 3009065
452 3363646
453 3113116
454 3382522
455 3080689
456 3509278
457 3112254
458 3458872
459 3217171
460 3521414
461 3181108
462 3608422
463 3216134
464 3594345
465 3331792
466 3614883
467 3286374
468 3750010
469 3321392
470 3698786
471 3436384
472 3754776
473 3393071
474 3855020
475 3436353
476 3836105
477 3546960
478 3856001
479 3503329
480 4006206
481 3540409
482 3938681
483 3661350
484 4002938
485 3621933
486 4107632
487 3653070
488 4087126
489 3778444
490 4110895
491 3728835
492 4263991
493 3767312
494 4191378
495 3900842
496 4259769
497 3844052
498 4372664
499 3883962
500 4355252
501 4017379
502 4366438
503 3962095
504 4529833
505 4010522
506 4454468
507 4139200
508 4528115
509 4082244
510 4652102
511 4122235
512 4617567
513 4263275
514 4635992
515 4212870
516 4814814
517 4244660
518 4726410
519 4391489
520 4809757
521 4328787
522 4927526
523 4370513
524 4898714
525 4529020
526 4914927
527 4454418
528 5102076
529 4497756
530 5018090
531 4650683
532 5089589
533 4582596
534 5222184
535 4636682
536 5186750
537 4785963
538 5203158
539 4711570
540 5412285
541 4758422
542 5301885
543 4921566
544 5384392
545 4857290
546 5523286
547 4891428
548 5487408
549 5058038
550 5510008
551 4981075
552 5715220
553 5026836
554 5603349
555 5211176
556 5692537
557 5118268
558 5836277
559 5163497
560 5804001
561 5341463
562 5810274
563 5257499
564 6037453
565 5317284
566 5914648
567 5485445
568 6006704
569 5399103
570 6172422
571 5446925
572 6113247
573 5634657
574 6126676
575 5555839
576 6365330
577 5591579
578 6235935
579 5783888
580 6346314
581 5688427
582 6495872
583 5736044
584 6443522
585 5946851
586 6455998
587 5836456
588 6709753
589 5886639
590 6580468
591 6089901
592 6668374
593 5986712
594 6836190
595 6052653
596 6784754
597 6246516
598 6792832
599 6138803
600 7075054
601 6191213
602 6908502
603 6403125
604 7016782
605 6308788
606 7194816
607 6346263
608 7132016
609 6566208
610 7157305
611 6449922
612 7424031
613 6504413
614 7260576
615 6745712
616 7369931
617 6610735
618 7560098
619 6664079
620 7510363
621 6893297
622 7500949
623 6772101
624 7797248
625 6845451
626 7622841
627 7061225
628 7740230
629 6935213
630 7949612
631 6991505
632 7864300
633 7234026
634 7869863
635 7121174
636 8185223
637 7157671
638 7993114
639 7404535
640 8134334
641 7270860
642 8322962
643 7327250
644 8245902
645 7601746
646 8248546
647 7440858
648 8577342
649 7497298
650 8396287
651 7760630
652 8506882
653 7614528
654 8720338
655 7694495
656 8636197
657 7937703
658 8639024
659 7789460
660 9005345
661 7849510
662 8771646
663 8119773
664 8904172
665 7991857
666 9127111
667 8027766
668 9040618
669 8306916
670 9061056
671 8145303
672 9404145
673 8208837
674 9175544
675 8516157
676 9313883
677 8330238
678 9548492
679 8393051
680 9475236
681 8684755
682 9448806
683 8514685
684 9832002
685 8603335
686 9590902
687 8876512
688 9734076
689 8700492
690 10002928
691 8765355
692 9878398
693 9069127
694 9872674
695 8918819
696 10274566
697 8955584
698 10015357
699 9268137
700 10193250
701 9083846
702 10417702
703 9148049
704 10309691
705 9496122
706 10305883
707 9280239
708 10727199
709 9343891
710 10479176
711 9668433
712 10609084
713 9474816
714 10874758
715 9567683
716 10759890
717 9875449
718 10748757
719 9673288
720 11213454
721 9744633
722 10899555
723 10082580
724 11063382
725 9907173
726 11336938
727 9943393
728 11215915
729 10290574
730 11234301
731 10079007
732 11665640
733 10148570
734 11357477
735 10538905
736 11526687
737 10284294
738 11812911
739 10355791
740 11716919
741 10717439
742 11671272
743 10494939
744 12151296
745 10600797
746 11827311
747 10934653
748 12000701
749 10709918
750 12334980
751 10778048
752 12164108
753 11156729
754 12144215
755 10956251
756 12649543
757 10992967
758 12307886
759 11376299
760 12525800
761 11136898
762 12802496
763 11213322
764 12656349
765 11638406
766 12634479
767 11353136
768 13158320
769 11429526
770 12836154
771 11832249
772 12990782
773 11576738
774 13310362
775 11690899
776 13159139
777 12066232
778 13133496
779 11799361
780 13716175
781 11873872
782 13301728
783 12292982
784 13502548
785 12069092
786 13836278
787 12103269
788 13672911
789 12529931
790 13684180
791 12259776
792 14210739
793 12331247
794 13817302
795 12810330
796 14022501
797 12486630
798 14372088
799 12563445
800 14239552
801 13007811
802 14166894
803 12717801
804 14761192
805 12850481
806 14341142
807 13252249
808 14555774
809 12956838
810 14956225
811 13036686
812 14740140
813 13498138
814 14697352
815 13242646
816 15317535
817 13275966
818 14880604
819 13748128
820 15146571
821 13437781
822 15475028
823 13518405
824 15285210
825 14043058
826 15249608
827 13681130
828 15886621
829 13763732
830 15477458
831 14251574
832 15654903
833 13933102
834 16045052
835 14062224
836 15842159
837 14506960
838 15801664
839 14176005
840 16524726
841 14261892
842 15990930
843 14767201
844 16226071
845 14479374
846 16625113
847 14517627
848 16418189
849 15029656
850 16421647
851 14682491
852 17066183
853 14768458
854 16567478
855 15345324
856 16808402
857 14940012
858 17216684
859 15025864
860 17056516
861 15568724
862 16950897
863 15198469
864 17670509
865 15344739
866 17147087
867 15829649
868 17404871
869 15458095
870 17884150
871 15546960
872 17601174
873 16102819
874 17541826
875 15793927
876 18292832
877 15815441
878 17742269
879 16378371
880 18058490
881 15993088
882 18452485
883 16083234
884 18204348
885 16717934
886 18147456
887 16262047
888 18926170
889 16362886
890 18412203
891 16934414
892 18620772
893 16534390
894 19079436
895 16691433
896 18835858
897 17219157
898 18762530
899 16809932
900 19627748
901 16902367
902 18968076
903 17517154
904 19251720
905 17156049
906 19724480
907 17181676
908 19460664
909 17795641
910 19461500
911 17368570
912 20226498
913 17461007
914 19602879
915 18156232
916 19890093
917 17662299
918 20376896
919 17746898
920 20176498
921 18384008
922 20030880
923 17934022
924 20900765
925 18106287
926 20247267
927 18680003
928 20544520
929 18225847
930 21119240
931 18333573
932 20764019
933 18981125
934 20682334
935 18586529
936 21577398
937 18615768
938 20912540
939 19284084
940 21282298
941 18811043
942 21731996
943 18908634
944 21434373
945 19675794
946 21344452
947 19107497
948 22274646
949 19204581
950 21646494
951 19898113
952 21899056
953 19406818
954 22424832
955 19587461
956 22115868
957 20206645
958 22023617
959 19720108
960 23060956
961 19811218
962 22249806
963 20523331
964 22577348
965 20095654
966 23143684
967 20115398
968 22810783
969 20838165
970 22795227
971 20319768
972 23703659
973 20437737
974 22945605
975 21240679
976 23283064
977 20630551
978 23853860
979 20731116
980 23612868
981 21484078
982 23414868
983 20942470
984 24443442
985 21137125
986 23649116
987 21822502
988 23991212
989 21257743
990 24667812
991 21364991
992 24240839
993 22137618
994 24141140
995 21667835
996 25188145
997 21683986
998 24368764
999 22467296
1000 24818923