0 0
1 1
2 4
3 9
4 19
5 30
6 52
7 70
8 107
9 136
10 191
11 226
12 314
13 352
14 463
15 523
16 664
17 717
18 919
19 964
20 1205
21 1282
22 1546
23 1603
24 1992
25 2009
26 2414
27 2504
28 2958
29 2974
30 3606
31 3553
32 4223
33 4273
34 4936
35 4912
36 5885
37 5685
38 6634
39 6654
40 7664
41 7454
42 8822
43 8454
44 9845
45 9746
46 11015
47 10684
48 12637
49 11939
50 13761
51 13523
52 15321
53 14660
54 17152
55 16203
56 18640
57 18122
58 20306
59 19417
60 22843
61 21205
62 24193
63 23563
64 26473
65 25098
66 29104
67 27092
68 31023
69 29877
70 33370
71 31499
72 36818
73 33882
74 38463
75 37240
76 41521
77 38938
78 45080
79 41590
80 47614
81 45393
82 50289
83 47265
84 55110
85 50461
86 56926
87 54619
88 60872
89 56637
90 65691
91 60055
92 68317
93 64938
94 71727
95 67247
96 78029
97 70774
98 79964
99 76339
100 85088
101 78533
102 90670
103 82594
104 93915
105 89219
106 97930
107 91095
108 105918
109 95565
110 108104
111 102522
112 113877
113 104823
114 120936
115 110036
116 124519
117 117436
118 129148
119 119773
120 139605
121 124991
122 140751
123 133485
124 147869
125 136258
126 156755
127 141428
128 160541
129 150846
130 166301
131 153060
132 177895
133 159301
134 179128
135 170117
136 187652
137 171653
138 197898
139 178105
140 202902
141 189429
142 207881
143 191459
144 222664
145 199164
146 223220
147 210887
148 232978
149 212606
150 246010
151 219967
152 249554
153 233404
154 256108
155 235971
156 273290
157 242930
158 273161
159 257313
160 285602
161 259182
162 298688
163 267178
164 302924
165 283939
166 309894
167 284059
168 330810
169 292888
170 330540
171 309814
172 342125
173 310706
174 358370
175 321531
176 362993
177 338095
178 370192
179 338684
180 395629
181 348480
182 392174
183 367864
184 406472
185 369739
186 424868
187 378445
188 429052
189 399799
190 438742
191 399160
192 464818
193 409889
194 460723
195 433885
196 477531
197 431621
198 498358
199 442766
200 504433
201 466616
202 510547
203 466022
204 542053
205 479303
206 536515
207 502740
208 555022
209 501099
210 581392
211 513295
212 582177
213 540217
214 590858
215 540298
216 627390
217 551501
218 619231
219 579396
220 642137
221 576728
222 666024
223 589871
224 670358
225 623267
226 678390
227 616836
228 718932
229 630661
230 712008
231 663697
232 731839
233 658690
234 761338
235 675996
236 763644
237 707062
238 773834
239 701977
240 822630
241 717055
242 806359
243 753223
244 830720
245 751454
246 863652
247 762670
248 866018
249 800571
250 878833
251 793821
252 927655
253 810100
254 910775
255 853726
256 938342
257 842322
258 973938
259 859910
260 979316
261 901515
262 984758
263 892328
264 1042518
265 913857
266 1024242
267 953927
268 1052339
269 944180
270 1097478
271 961929
272 1093121
273 1009965
274 1102127
275 1002650
276 1165405
277 1016170
278 1142904
279 1065439
280 1182411
281 1053219
282 1218784
283 1071973
284 1217507
285 1128564
286 1227666
287 1111541
288 1298690
289 1129796
290 1276769
291 1183520
292 1305644
293 1168974
294 1354986
295 1194783
296 1351906
297 1246375
298 1360665
299 1229657
300 1444051
301 1252178
302 1406939
303 1309303
304 1445457
305 1298427
306 1497200
307 1313409
308 1494702
309 1375120
310 1509208
311 1356323
312 1587866
313 1378347
314 1551124
315 1452281
316 1591752
317 1422575
318 1648110
319 1445257
320 1651452
321 1512397
322 1654122
323 1490477
324 1745063
325 1521446
326 1703790
327 1583770
328 1748593
329 1562499
330 1817402
331 1584219
332 1801202
333 1658119
334 1810105
335 1640130
336 1914765
337 1656644
338 1865005
339 1732613
340 1920867
341 1706084
342 1978806
343 1733172
344 1969902
345 1819260
346 1977118
347 1781158
348 2086403
349 1806882
350 2047145
351 1890669
352 2087008
353 1858804
354 2156074
355 1894699
356 2144467
357 1973779
358 2152476
359 1937901
360 2284911
361 1965343
362 2213095
363 2054752
364 2270129
365 2029973
366 2343516
367 2047116
368 2331258
369 2140933
370 2348568
371 2105852
372 2465544
373 2131221
374 2400874
375 2238626
376 2459722
377 2188390
378 2544712
379 2217091
380 2536185
381 2317048
382 2530403
383 2275172
384 2671078
385 2321305
386 2596910
387 2409922
388 2657966
389 2364691
390 2759810
391 2395114
392 2732788
393 2502443
394 2732779
395 2468941
396 2884314
397 2487134
398 2802247
399 2601917
400 2884396
401 2549539
402 2961664
403 2581308
404 2939190
405 2711808
406 2948706
407 2645408
408 3107588
409 2677365
410 3032549
411 2796321
412 3086286
413 2746401
414 3188239
415 2790284
416 3164376
417 2898630
418 3166118
419 2841534
420 3359237
421 2875762
422 3241322
423 3004537
424 3317397
425 2959513
426 3421702
427 2982465
428 3392770
429 3110673
430 3413438
431 3046942
432 3585253
433 3082395
434 3479884
435 3235646
436 3552744
437 3152970
438 3666238
439 3188451
440 3656752
441 3336520
442 3636497
443 3260786
444 3833028
445 3315721
446 3717859
447 3442259
448 3809143
449 3370823
450 3943688
451 3409137
452 3885195
453 3557798
454 3885312
455 3508179
456 4099382
457 3521289
458 3970648
459 3677541
460 4079228
461 3597395
462 4193246
463 3636067
464 4149554
465 3816268
466 4144861
467 3713655
468 4371845
469 3759434
470 4256198
471 3917470
472 4329156
473 3833531
474 4460976
475 3894478
476 4423557
477 4044321
478 4413897
479 3953036
480 4681138
481 3995061
482 4506031
483 4175086
484 4604012
485 4099625
486 4749210
487 4118035
488 4701592
489 4297374
490 4726045
491 4201534
492 4946799
493 4244214
494 4788990
495 4457140
496 4895256
497 4336498
498 5042300
499 4372303
500 5015750
501 4562335
502 4982308
503 4458366
504 5266683
505 4528816
506 5082736
507 4698763
508 5188532
509 4590511
510 5377630
511 4643083
512 5295233
513 4839593
514 5281916
515 4752088
516 5566812
517 4771726
518 5392402
519 4976681
520 5532715
521 4861484
522 5669038
523 4907340
524 5601825
525 5157494
526 5591639
527 4999968
528 5899902
529 5047070
530 5728854
531 5268416
532 5825249
533 5141862
534 5993320
535 5218988
536 5929606
537 5412823
538 5911374
539 5294481
540 6267915
541 5333109
542 6020753
543 5562636
544 6150980
545 5461768
546 6342782
547 5479029
548 6257065
549 5718807
550 6279106
551 5577599
552 6584632
553 5637666
554 6354671
555 5904148
556 6485046
557 5727711
558 6684981
559 5779153
560 6654977
561 6029821
562 6583626
563 5880226
564 6937877
565 5967338
566 6699150
567 6201556
568 6841936
569 6035272
570 7081250
571 6087604
572 6957791
573 6349169
574 6946208
575 6229348
576 7320230
577 6245880
578 7054921
579 6513562
580 7238292
581 6363239
582 7413512
583 6407618
584 7326968
585 6725843
586 7297386
587 6513793
588 7702776
589 6568951
590 7463252
591 6850389
592 7577345
593 6678063
594 7803086
595 6786811
596 7696555
597 7022650
598 7671536
599 6844310
600 8136830
601 6901462
602 7810774
603 7201690
604 7953441
605 7058817
606 8190496
607 7070866
608 8091694
609 7386852
610 8101575
611 7186476
612 8494428
613 7243502
614 8184954
615 7598420
616 8372693
617 7359564
618 8595994
619 7417806
620 8531155
621 7740775
622 8449761
623 7548877
624 8915254
625 7642220
626 8583987
627 7922591
628 8753495
629 7714469
630 9085856
631 7774920
632 8900536
633 8107376
634 8855917
635 7943832
636 9333415
637 7972610
638 8996254
639 8302232
640 9234168
641 8079471
642 9441686
643 8140951
644 9328248
645 8540546
646 9273950
647 8264779
648 9788795
649 8330900
650 9472509
651 8699522
652 9599753
653 8453887
654 9881666
655 8570203
656 9754682
657 8887150
658 9718776
659 8644421
660 10287651
661 8709693
662 9847392
663 9082411
664 10049060
665 8910471
666 10340921
667 8903844
668 10188253
669 9283250
670 10202240
671 9036823
672 10718487
673 9100730
674 10290932
675 9553817
676 10492441
677 9232829
678 10797436
679 9316939
680 10718320
681 9696683
682 10596366
683 9433444
684 11172399
685 9561727
686 10765370
687 9906482
688 10965481
689 9638750
690 11340540
691 9705894
692 11110675
693 10148723
694 11055728
695 9905607
696 11664634
697 9913798
698 11212187
699 10334673
700 11517443
701 10051973
702 11771118
703 10122409
704 11605384
705 10619542
706 11530477
707 10282471
708 12153303
709 10334364
710 11762000
711 10781822
712 11927118
713 10476738
714 12283226
715 10621769
716 12079833
717 10998017
718 12015641
719 10692077
720 12763047
721 10787237
722 12181427
723 11224142
724 12413211
725 10981700
726 12776940
727 10985104
728 12619477
729 11461530
730 12591055
731 11133643
732 13191086
733 11207645
734 12681837
735 11780189
736 12937887
737 11361216
738 13306433
739 11432370
740 13176407
741 11921625
742 13047160
743 11583266
744 13742036
745 11735769
746 13195621
747 12164602
748 13450445
749 11835664
750 13918108
751 11890077
752 13637689
753 12395681
754 13546305
755 12122115
756 14313721
757 12122932
758 13720856
759 12642093
760 14081828
761 12278901
762 14383212
763 12381836
764 14160662
765 12976036
766 14077631
767 12517530
768 14856537
769 12595801
770 14378482
771 13131541
772 14526995
773 12755249
774 14954636
775 12919888
776 14727031
777 13407792
778 14622524
779 12997337
780 15512257
781 13084146
782 14808172
783 13645338
784 15130589
785 13330082
786 15518970
787 13325084
788 15273938
789 13891011
790 15275204
791 13516226
792 16037173
793 13576439
794 15368594
795 14241830
796 15656438
797 13739873
798 16134880
799 13824825
800 15966922
801 14423490
802 15749798
803 13997673
804 16604778
805 14200263
806 15944830
807 14676549
808 16256736
809 14248305
810 16820019
811 14334579
812 16468166
813 14943836
814 16336608
815 14602528
816 17239103
817 14594408
818 16527688
819 15258078
820 16942091
821 14768042
822 17316676
823 14855192
824 17054738
825 15593820
826 16957552
827 15031011
828 17858504
829 15120183
830 17235030
831 15762408
832 17467094
833 15329491
834 17941292
835 15490102
836 17655839
837 16053808
838 17530794
839 15565556
840 18655058
841 15658112
842 17736690
843 16322253
844 18064492
845 15947231
846 18592669
847 15968120
848 18295850
849 16607062
850 18267997
851 16112707
852 19138619
853 16205005
854 18394094
855 17018922
856 18719142
857 16390131
858 19239676
859 16482797
860 19033138
861 17218628
862 18781101
863 16669072
864 19841999
865 16877719
866 18994409
867 17477386
868 19381655
869 16958455
870 20020534
871 17050866
872 19584552
873 17786490
874 19425606
875 17390429
876 20484722
877 17334382
878 19641453
879 18069935
880 20162556
881 17525991
882 20626139
883 17623131
884 20231022
885 18494870
886 20081590
887 17816006
888 21200322
889 17952240
890 20435165
891 18698523
892 20675759
893 18111136
894 21260560
895 18333269
896 20967818
897 18987895
898 20749734
899 18406474
900 22039353
901 18508595
902 20983824
903 19333202
904 21384446
905 18834977
906 21964964
907 18806845
908 21590527
909 19622036
910 21618688
911 19008175
912 22631488
913 19118095
914 21661929
915 20056620
916 22057896
917 19353959
918 22699688
919 19415571
920 22464282
921 20242090
922 22126344
923 19623988
924 23390307
925 19861030
926 22361043
927 20579932
928 22796412
929 19931204
930 23563388
931 20079398
932 23008694
933 20888221
934 22833004
935 20393015
936 24133752
937 20350763
938 23119104
939 21215922
940 23647256
941 20560956
942 24155388
943 20666716
944 23765132
945 21755582
946 23563076
947 20879896
948 24845020
949 20991641
950 23955860
951 21879929
952 24307728
953 21201853
954 24931804
955 21458189
956 24478391
957 22225183
958 24286861
959 21571222
960 25816354
961 21636672
962 24539742
963 22574696
964 24979813
965 22005992
966 25734844
967 21963811
968 25271234
969 22901399
970 25201109
971 22183577
972 26429030
973 22343585
974 25285489
975 23408467
976 25775739
977 22517568
978 26467344
979 22637930
980 26226299
981 23613339
982 25793562
983 22852851
984 27241066
985 23127921
986 26050788
987 23994830
988 26525942
989 23192451
990 27476768
991 23306722
992 26816547
993 24299364
994 26620972
995 23699471
996 28027597
997 23649413
998 26826010
999 24676168
1000 27525505