1 0
2 1
3 5
4 11
5 35
6 37
7 93
8 103
9 195
10 293
11 287
12 365
13 501
14 551
15 807
16 985
17 1231
18 845
19 1447
20 1715
21 1417
22 2235
23 2615
24 2793
25 2901
26 3321
27 3579
28 4399
29 3485
30 3989
31 4595
32 5491
33 6373
34 6395
35 8125
36 7679
37 8229
38 8599
39 10147
40 10381
41 11763
42 9937
43 12375
44 10345
45 14113
46 13715
47 14219
48 17687
49 17467
50 17777
51 19929
52 20411
53 16077
54 21631
55 20417
56 25807
57 24209
58 22959
59 25533
60 23989
61 26163
62 31077
63 33115
64 32179
65 30781
66 34949
67 35883
68 37521
69 38483
70 39837
71 36849
72 45235
73 48923
74 48601
75 44691
76 48703
77 48893
78 46525
79 51845
80 54661
81 61211
82 50509
83 62919
84 62829
85 65095
86 65787
87 64457
88 67181
89 69125
90 67143
91 76607
92 79823
93 81399
94 75571
95 81667
96 88159
97 96401
98 92337
99 85423
100 90221
101 92443
102 108601
103 111075
104 110493
105 110591
106 113045
107 116367
108 105069
109 124751
110 114905
111 127259
112 126161
113 127333
114 123535
115 120043
116 141397
117 145595
118 137763
119 139649
120 149983
121 146685
122 139809
123 148145
124 159747
125 155111
126 170393
127 174441
128 178827
129 173091
130 183577
131 190831
132 195015
133 184407
134 182581
135 182941
136 190825
137 203801
138 211463
139 218489
140 229865
141 206227
142 220133
143 218595
144 231991
145 223997
146 244303
147 240829
148 262441
149 245283
150 269103
151 251321
152 260533
153 263667
154 279191
155 272659
156 282427
157 277783
158 294273
159 277341
160 261581
161 297899
162 294005
163 299719
164 321231
165 324469
166 325411
167 327891
168 328553
169 318381
170 326097
171 371203
172 339353
173 345179
174 368413
175 359087
176 374485
177 358167
178 360021
179 363047
180 380377
181 394971
182 413099
183 368233
184 408509
185 423243
186 406653
187 419657
188 445599
189 429185
190 455727
191 427709
192 451919
193 443555
194 476473
195 452883
196 501165
197 472417
198 500929
199 495409
200 513115
201 494781
202 535199
203 520769
204 486093
205 555343
206 522461
207 541215
208 554759
209 557885
210 551431
211 556637
212 558029
213 575183
214 579775
215 600375
216 524953
217 572991
218 608213
219 636391
220 611369
221 596481
222 671903
223 688189
224 686739
225 709143
226 666449
227 713693
228 715707
229 695143
230 659419
231 703221
232 712483
233 678959
234 752261
235 751731
236 739751
237 740757
238 762049
239 753011
240 783815
241 796519
242 732339
243 766391
244 804157
245 798037
246 813275
247 827031
248 782259
249 847335
250 829039
251 863825
252 839137
253 840203
254 886001
255 823241
256 899383
257 841961
258 880187
259 880521
260 916721
261 976027
262 914003
263 918637
264 955497
265 1001997
266 971907
267 981605
268 946325
269 912215
270 1044001
271 998721
272 1082839
273 1058425
274 1023631
275 1016617
276 1035827
277 1053511
278 1074261
279 1067861
280 1111047
281 1120007
282 1105415
283 1163363
284 1141577
285 1138143
286 1175647
287 1134225
288 1123121
289 1183455
290 1241409
291 1178781
292 1199555
293 1233661
294 1207067
295 1239453
296 1301097
297 1176947
298 1328329
299 1330807
300 1338219
301 1314145
302 1325141
303 1344927
304 1319859
305 1332139
306 1307553
307 1413095
308 1379165
309 1437055
310 1418041
311 1391871
312 1435785
313 1405289
314 1448779
315 1484443
316 1388013
317 1485295
318 1483959
319 1502373
320 1515665
321 1548119
322 1559733
323 1539705
324 1483707
325 1518261
326 1505097
327 1541083
328 1626935
329 1717459
330 1659517
331 1627097
332 1696505
333 1631271
334 1752535
335 1630899
336 1761999
337 1693581
338 1742877
339 1722293
340 1725107
341 1778577
342 1733965
343 1740281
344 1778939
345 1829493
346 1896911
347 1733149
348 1822175
349 1851155
350 1919545
351 1956279
352 1825093
353 1890917
354 1878211
355 1918337
356 1881793
357 2016115
358 1932479
359 2014341
360 1984159
361 1941501
362 2032965
363 2035895
364 2063527
365 1974259
366 1952337
367 1996353
368 2037955
369 2021909
370 2052211
371 2195155
372 2185275
373 2118253
374 2187091
375 2179365
376 2276187
377 2218975
378 2164321
379 2221889
380 2190369
381 2211445
382 2326845
383 2364407
384 2375557
385 2378647
386 2433595
387 2388519
388 2413625
389 2474271
390 2447987
391 2398481
392 2415301
393 2530231
394 2437171
395 2499351
396 2445433
397 2448907
398 2605269
399 2403355
400 2525141
401 2587613
402 2448761
403 2589747
404 2553801
405 2692441
406 2576399
407 2579525
408 2596521
409 2617191
410 2569107
411 2710981
412 2766353
413 2730671
414 2663203
415 2577765
416 2689001
417 2786959
418 2869547
419 2760549
420 2881499
421 2807793
422 2670809
423 2810075
424 2926923
425 2945637
426 2811861
427 2968155
428 3052457
429 2870331
430 2986207
431 3041701
432 3046075
433 3076523
434 3079187
435 3118265
436 3047361
437 3078177
438 3106009
439 3137323
440 3157163
441 3170507
442 3175581
443 3293653
444 3323263
445 3091793
446 3234821
447 3387055
448 3492495
449 3202697
450 3354405
451 3462563
452 3382903
453 3381687
454 3426617
455 3462013
456 3465541
457 3546717
458 3439447
459 3510737
460 3651109
461 3557943
462 3579863
463 3592407
464 3684833
465 3738471
466 3650409
467 3664387
468 3779195
469 3696021
470 3841787
471 3666983
472 3796687
473 3760631
474 3685293
475 3849651
476 3712497
477 3776437
478 3810307
479 3933623
480 3825709
481 3751949
482 4102697
483 3888385
484 4016081
485 3949519
486 4006783
487 3989809
488 4000751
489 4006163
490 3950899
491 4231437
492 4146927
493 4138041
494 4094349
495 4104967
496 4124281
497 4152207
498 4204469
499 4404403
500 4224723
501 4339449
502 4335083
503 4437865
504 4448575
505 4423541
506 4378165
507 4201927
508 4457895
509 4440449
510 4506103
511 4364179
512 4559823
513 4468733
514 4574709
515 4545087
516 4498193
517 4536365
518 4661201
519 4599187
520 4521407
521 4675613
522 4713027
523 4701389
524 4622707
525 4821509
526 4898783
527 4691881
528 4683785
529 4742391
530 4928877
531 4850451
532 5039941
533 4921511
534 4827283
535 4741457
536 5080631
537 4917101
538 4852005
539 4991901
540 4916667
541 5069971
542 4936761
543 5253367
544 5166647
545 5278289
546 5288235
547 5265055
548 4998123
549 5303547
550 5367145
551 5335221
552 5413863
553 5434615
554 5462761
555 5320447
556 5400637
557 5358335
558 5507013
559 5310835
560 5603809
561 5527001
562 5570679
563 5569547
564 5518329
565 5673747
566 5595887
567 5624639
568 5721017
569 5661049
570 5988383
571 5619033
572 5862685
573 5881071
574 5679937
575 5589381
576 6054767
577 5758321
578 5923435
579 6138793
580 6092735
581 5939713
582 5936759
583 6269541
584 5948783
585 5998925
586 5902191
587 6156489
588 6293795
589 6142737
590 6338485
591 6028711
592 6380385
593 6425615
594 6341957
595 6214453
596 6378575
597 6305185
598 6543995
599 6572833
600 6534269
601 6674277
602 6500627
603 6565285
604 6781419
605 6405595
606 6881681
607 6541635
608 6553669
609 6714839
610 6627885
611 6709015
612 6710921
613 6828609
614 6865187
615 6982411
616 6873579
617 6720009
618 6823481
619 7039787
620 6930671
621 7028187
622 6932801
623 7188251
624 6753745
625 7175921
626 7252239
627 7182507
628 7077497
629 7198527
630 7225805
631 7126715
632 7341445
633 7318859
634 7259331
635 7727755
636 7558261
637 7408431
638 7520609
639 7317573
640 7575579
641 7504623
642 7608839
643 8075219
644 7549909
645 7698473
646 7601387
647 7672973
648 7579069
649 7743597
650 7785923
651 7748877
652 7868147
653 7808433
654 7931209
655 7899135
656 7962825
657 8249851
658 7986319
659 8230569
660 8156805
661 8188523
662 7946263
663 8288841
664 8116691
665 8201821
666 8034581
667 8551631
668 8579885
669 8375643
670 7997471
671 8411793
672 8382215
673 8521717
674 8534411
675 8732723
676 8587523
677 8363243
678 8569745
679 8566161
680 8656807
681 8630631
682 8601841
683 8624907
684 8615245
685 8814007
686 9159191
687 8782553
688 8931275
689 8712591
690 8952395
691 8730881
692 8998949
693 8976521
694 9162003
695 9390187
696 8949749
697 9152413
698 9151689
699 9419857
700 9339147
701 9142061
702 9476633
703 9131011
704 9520025
705 9489307
706 9566393
707 9760423
708 9488623
709 9918101
710 9525031
711 9796797
712 9908987
713 9580631
714 10021697
715 10072345
716 9603751
717 9787883
718 10017093
719 9484973
720 9812903
721 9863193
722 10041371
723 10138197
724 10174999
725 10234547
726 10027113
727 10266371
728 10025559
729 10268767
730 9708001
731 10253807
732 10047295
733 10266985
734 10531835
735 10201033
736 10325769
737 10480757
738 10419659
739 10517411
740 10999283
741 10329657
742 10607307
743 10553951
744 10808541
745 10751705
746 10734019
747 10789445
748 10753275
749 10857553
750 11007753
751 10546597
752 10956479
753 11108477
754 10879593
755 10708513
756 10981643
757 11144133
758 11218935
759 10856407
760 10876387
761 11485289
762 11517223
763 11551169
764 11452057
765 11455115
766 11554659
767 11334451
768 11561189
769 11388223
770 11390833
771 11589921
772 11565739
773 11383049
774 11747751
775 11525557
776 11264849
777 11948087
778 11846363
779 11858315
780 11954495
781 11852681
782 11717345
783 11799999
784 11915351
785 12060543
786 12217833
787 12322801
788 11928983
789 12289835
790 12186537
791 12247843
792 12290333
793 12269939
794 12362725
795 12374259
796 12458049
797 12551829
798 12418289
799 12436263
800 12528537
801 12687023
802 12178831
803 12519531
804 12776261
805 12676949
806 12573567
807 12799147
808 12902435
809 12641217
810 12694093
811 13181029
812 12889903
813 12862273
814 13043207
815 13045293
816 12976479
817 13177257
818 13115171
819 13460591
820 13208949
821 13188543
822 13297537
823 13242755
824 13159137
825 13385881
826 13249307
827 13549053
828 13670695
829 13745929
830 13574555
831 13493957
832 13486967
833 13570993
834 13206029
835 13671749
836 13186895
837 14202257
838 13824663
839 13820125
840 13859041
841 13767589
842 13581487
843 13870921
844 14194661
845 14519051
846 14412159
847 14300881
848 14616431
849 14300529
850 13875939
851 14492705
852 14438709
853 14849711
854 14819307
855 14362511
856 14698721
857 14809693
858 15008911
859 14510413
860 15112409
861 15093919
862 14540257
863 14896959
864 14807041
865 15053175
866 14935629
867 15523407
868 14984573
869 15020185
870 15232925
871 15414831
872 15350399
873 15638001
874 15137311
875 15113661
876 15877727
877 15653851
878 15849891
879 15561269
880 15411385
881 15522797
882 16174785
883 15999335
884 15813665
885 15678411
886 15477431
887 15713087
888 15457079
889 15953595
890 15597493
891 16573579
892 16200081
893 16065315
894 15987537
895 15938331
896 16489563
897 15960533
898 16044687
899 16074103
900 16436925
901 16027369
902 16640473
903 16447479
904 16482091
905 16343895
906 16629367
907 16292441
908 16641161
909 16546935
910 16996959
911 16805085
912 17076029
913 16722827
914 16578113
915 16776175
916 16882299
917 17073601
918 17096947
919 17125477
920 18029699
921 17260551
922 17081493
923 17276379
924 17435253
925 16855397
926 17282919
927 18078867
928 17553585
929 17767451
930 17211613
931 17772883
932 17808345
933 17592033
934 17614115
935 17953237
936 18299109
937 17693299
938 17952585
939 17814453
940 18561623
941 18153973
942 18022469
943 18620183
944 18759541
945 18354299
946 18296149
947 18813025
948 19009527
949 18017453
950 18907507
951 19307275
952 18607365
953 18603679
954 18891209
955 18472729
956 18896089
957 19105327
958 19306309
959 19355187
960 18653709
961 19214949
962 19749125
963 19045891
964 19223245
965 18762579
966 19743771
967 19717631
968 19064073
969 19204983
970 19744739
971 19642529
972 19790833
973 19498609
974 19626757
975 19951243
976 19519847
977 19579435
978 19846007
979 19621005
980 19393191
981 20070479
982 19839549
983 20109489
984 20404101
985 19686435
986 20777225
987 19803469
988 20344117
989 20048179
990 20089717
991 20002665
992 21045009
993 20431531
994 20771885
995 20832517
996 20315619
997 20821187
998 20741433
999 20878379
1000 21223887