1 0
2 0
3 0
4 1
5 1
6 1
7 1
8 2
9 1
10 2
11 1
12 3
13 2
14 4
15 3
16 6
17 4
18 6
19 5
20 9
21 7
22 9
23 8
24 13
25 10
26 13
27 11
28 18
29 14
30 19
31 16
32 26
33 20
34 27
35 23
36 35
37 29
38 38
39 33
40 48
41 39
42 51
43 44
44 62
45 53
46 68
47 60
48 82
49 69
50 87
51 77
52 103
53 90
54 111
55 100
56 131
57 113
58 138
59 124
60 161
61 142
62 172
63 156
64 201
65 175
66 211
67 191
68 244
69 217
70 260
71 237
72 299
73 264
74 316
75 287
76 360
77 322
78 384
79 351
80 437
81 389
82 461
83 422
84 521
85 470
86 553
87 509
88 622
89 560
90 657
91 604
92 734
93 666
94 779
95 719
96 869
97 787
98 916
99 847
100 1016
101 929
102 1075
103 998
104 1188
105 1085
106 1252
107 1162
108 1376
109 1265
110 1455
111 1355
112 1597
113 1466
114 1679
115 1566
116 1835
117 1697
118 1934
119 1810
120 2109
121 1948
122 2214
123 2072
124 2405
125 2233
126 2531
127 2375
128 2748
129 2547
130 2878
131 2703
132 3115
133 2904
134 3270
135 3079
136 3534
137 3290
138 3698
139 3481
140 3985
141 3725
142 4179
143 3942
144 4501
145 4202
146 4703
147 4439
148 5054
149 4738
150 5289
151 5002
152 5678
153 5318
154 5927
155 5605
156 6349
157 5965
158 6638
159 6287
160 7108
161 6671
162 7411
163 7022
164 7920
165 7459
166 8270
167 7848
168 8830
169 8309
170 9201
171 8731
172 9805
173 9252
174 10231
175 9722
176 10897
177 10275
178 11344
179 10784
180 12063
181 11406
182 12570
183 11966
184 13357
185 12623
186 13893
187 13227
188 14740
189 13961
190 15346
191 14627
192 16275
193 15406
194 16912
195 16125
196 17910
197 16994
198 18628
199 17781
200 19713
201 18697
202 20473
203 19544
204 21635
205 20560
206 22487
207 21489
208 23752
209 22564
210 24647
211 23562
212 26002
213 24750
214 26997
215 25835
216 28463
217 27087
218 29514
219 28249
220 31080
221 29625
222 32245
223 30890
224 33942
225 32345
226 35166
227 33700
228 36976
229 35297
230 38329
231 36763
232 40277
233 38442
234 41705
235 40008
236 43777
237 41843
238 45350
239 43540
240 47583
241 45474
242 49232
243 47284
244 51607
245 49393
246 53413
247 51341
248 55960
249 53555
250 57860
251 55627
252 60563
253 58032
254 62640
255 60265
256 65544
257 62796
258 67718
259 65171
260 70797
261 67919
262 73169
263 70466
264 76459
265 73344
266 78951
267 76047
268 82432
269 79162
270 85145
271 82066
272 88870
273 85336
274 91705
275 88415
276 95647
277 91949
278 98720
279 95239
280 102922
281 98937
282 106143
283 102418
284 110582
285 106403
286 114070
287 110128
288 118808
289 114307
290 122451
291 118249
292 127453
293 122750
294 131391
295 126952
296 136709
297 131655
298 140832
299 136094
300 146437
301 141148
302 150888
303 145886
304 156853
305 151175
306 161495
307 156177
308 167782
309 161855
310 172778
311 167173
312 179449
313 173100
314 184670
315 178705
316 191692
317 185054
318 197306
319 191019
320 204765
321 197657
322 210615
323 203944
324 218463
325 211052
326 224745
327 217723
328 233054
329 225134
330 239615
331 232156
332 248346
333 240076
334 255383
335 247535
336 264635
337 255805
338 271962
339 263653
340 281684
341 272483
342 289523
343 280792
344 299798
345 289993
346 307976
347 298724
348 318760
349 308529
350 327503
351 317781
352 338909
353 328012
354 348009
355 337734
356 359975
357 348631
358 369690
359 358906
360 382313
361 370250
362 392440
363 381034
364 405667
365 393097
366 416469
367 404503
368 430430
369 417073
370 441662
371 429039
372 456289
373 442396
374 468246
375 455019
376 483652
377 468912
378 496100
379 482139
380 512225
381 496879
382 525467
383 510840
384 542461
385 526186
386 556219
387 540813
388 574000
389 557088
390 588619
391 572494
392 607316
393 589406
394 622525
395 605531
396 642069
397 623441
398 658216
399 640435
400 678776
401 659063
402 695541
403 676844
404 717030
405 696557
406 734798
407 715254
408 757362
409 735727
410 775831
411 755271
412 799393
413 776906
414 818955
415 797466
416 843705
417 819953
418 864006
419 841442
420 889841
421 865194
422 911320
423 887758
424 938407
425 912405
426 960717
427 935967
428 988966
429 961969
430 1012554
431 986719
432 1042179
433 1013716
434 1066638
435 1039551
436 1097528
437 1068014
438 1123350
439 1095101
440 1155695
441 1124615
442 1182489
443 1152864
444 1216189
445 1183944
446 1244459
447 1213569
448 1279756
449 1245814
450 1309049
451 1276704
452 1345812
453 1310646
454 1376691
455 1342991
456 1415133
457 1378157
458 1447154
459 1411857
460 1487162
461 1448833
462 1520893
463 1484130
464 1562736
465 1522459
466 1597664
467 1559222
468 1641204
469 1599499
470 1677949
471 1637941
472 1723423
473 1679646
474 1761497
475 1719654
476 1808781
477 1763431
478 1848814
479 1805274
480 1898207
481 1850624
482 1939638
483 1894164
484 1990979
485 1941747
486 2034505
487 1987221
488 2088060
489 2036453
490 2133130
491 2083737
492 2188757
493 2135344
494 2236078
495 2184737
496 2294110
497 2238150
498 2343046
499 2289491
500 2403311
501 2345451
502 2454633
503 2399006
504 2517429
505 2456866
506 2570525
507 2512493
508 2635696
509 2573056
510 2691353
511 2631088
512 2759272
513 2693728
514 2816789
515 2753993
516 2887255
517 2819537
518 2947504
519 2882333
520 3020848
521 2950051
522 3083141
523 3015222
524 3159188
525 3086019
526 3224404
527 3153938
528 3303566
529 3227107
530 3370917
531 3297573
532 3452983
533 3374032
534 3523423
535 3447376
536 3608759
537 3526327
538 3681536
539 3602374
540 3769951
541 3684806
542 3846034
543 3763968
544 3937983
545 3849113
546 4016515
547 3931179
548 4111754
549 4020049
550 4193800
551 4105385
552 4292737
553 4197090
554 4377454
555 4285505
556 4479872
557 4381152
558 4568340
559 4473101
560 4674743
561 4571821
562 4765997
563 4667060
564 4876125
565 4769982
566 4971337
567 4868919
568 5085644
569 4975062
570 5183883
571 5077480
572 5302132
573 5188062
574 5404593
575 5294465
576 5527343
577 5408535
578 5632970
579 5518663
580 5759922
581 5637471
582 5870027
583 5751778
584 6001682
585 5874229
586 6115228
587 5992478
588 6251322
589 6119931
590 6369633
591 6242681
592 6510781
593 6374072
594 6632679
595 6501024
596 6778565
597 6637733
598 6905482
599 6769388
600 7056657
601 6910220
602 7187462
603 7046314
604 7343639
605 7192751
606 7479785
607 7333899
608 7641640
609 7484787
610 7781848
611 7630673
612 7949021
613 7787526
614 8094878
615 7938701
616 8267978
617 8100196
618 8418228
619 8256373
620 8596933
621 8424155
622 8753183
623 8586010
624 8938237
625 8758788
626 9099061
627 8925961
628 9290080
629 9105410
630 9457215
631 9278510
632 9654872
633 9463180
634 9826939
635 9641885
636 10030883
637 9833577
638 10209650
639 10018631
640 10420702
641 10215937
642 10604613
643 10406956
644 10822336
645 10611721
646 11013322
647 10809378
648 11238456
649 11019993
650 11434989
651 11223937
652 11667145
653 11442400
654 11871175
655 11653452
656 12111251
657 11878197
658 12321054
659 12095920
660 12568589
661 12328974
662 12786264
663 12554108
664 13042069
665 12793723
666 13265955
667 13025879
668 13529608
669 13274225
670 13761836
671 13514301
672 14034319
673 13769684
674 14273024
675 14017219
676 14553816
677 14281854
678 14801312
679 14537659
680 15091305
681 14809621
682 15345757
683 15073274
684 15644481
685 15354958
686 15908233
687 15627441
688 16216762
689 15916964
690 16487749
691 16197756
692 16805530
693 16497554
694 17086271
695 16787547
696 17414283
697 17095523
698 17702776
699 17394247
700 18040510
701 17713007
702 18339317
703 18021536
704 18687948
705 18349039
706 18994832
707 18666820
708 19353738
709 19005729
710 19671475
711 19333741
712 20041725
713 19681750
714 20368115
715 20019484
716 20749149
717 20379459
718 21086996
719 20728090
720 21480093
721 21097780
722 21826936
723 21456686
724 22231439
725 21838999
726 22590283
727 22209249
728 23007356
729 22601689
730 23375820
731 22982723
732 23804859
733 23388390
734 24185990
735 23781487
736 24628386
737 24197956
738 25019532
739 24602459
740 25474551
741 25032889
742 25879001
743 25449962
744 26347913
745 25891624
746 26763059
747 26320663
748 27245198
749 26776952
750 27674367
751 27219348
752 28171246
753 27687594
754 28611525
755 28142613
756 29122365
757 28626265
758 29577316
759 29095177
760 30103502
761 29591277
762 30570295
763 30073416
764 31111108
765 30585641
766 31593360
767 31082520
768 32150448
769 31607987
770 32645013
771 32118827
772 33217507
773 32661288
774 33728287
775 33187474
776 34317693
777 33743693
778 34841594
779 34284506
780 35447125
781 34858506
782 35988088
783 35415594
784 36611529
785 36004213
786 37166113
787 36576707
788 37806548
789 37184023
790 38378960
791 37773429
792 39038023
793 38395954
794 39624926
795 39001485
796 40301770
797 39643554
798 40907430
799 40266995
800 41603987
801 40925211
802 42224709
803 41565646
804 42939963
805 42244422
806 43580329
807 42903485
808 44316056
809 43599026
810 44972427
811 44275870
812 45727698
813 44992900
814 46404711
815 45689457
816 47181617
817 46424255
818 47875236
819 47139509
820 48672702
821 47896871
822 49387869
823 48632598
824 50207822
825 49408429
826 50940606
827 50163700
828 51782048
829 50963093
830 52537465
831 51739999
832 53402659
833 52558954
834 54176373
835 53356420
836 55064131
837 54200125
838 55861520
839 55020078
840 56773925
841 55884084
842 57590720
843 56725526
844 58526687
845 57615367
846 59368319
847 58480561
848 60330288
849 59391881
850 61192044
851 60279639
852 62178763
853 61218046
854 63066418
855 62130451
856 64080134
857 63091168
858 64989104
859 64027135
860 66028655
861 65016101
862 66964789
863 65978070
864 68032803
865 66990624
866 68991059
867 67977343
868 70086160
869 69019522
870 71072789
871 70033238
872 72197404
873 71099876
874 73207441
875 72139427
876 74360305
877 73236955
878 75400070
879 74304969
880 76584014
881 75428319
882 77648035
883 76523420
884 78861604
885 77679115
886 79956594
887 78803730
888 81202408
889 79986219
890 82323027
891 81139083
892 83599731
893 82355272
894 84752785
895 83539216
896 86063431
897 84783675
898 87243058
899 85997244
900 88586049
901 87277000
902 89799518
903 88522814
904 91177675
905 89831863
906 92419213
907 91108567
908 93831070
909 92454379
910 95108016
911 93765025
912 96556849
913 95141716
914 97862864
915 96484707
916 99346994
917 97899840
918 100689854
919 99277997
920 102212313
921 100725151
922 103585841
923 102137008
924 105145063
925 103624170
926 106557133
927 105073003
928 108156632
929 106593896
930 109600485
931 108078026
932 111238426
933 109640762
934 112722443
935 111163221
936 114402089
937 112760885
938 115919606
939 114320107
940 117639260
941 115961311
942 119198751
943 117560810
944 120962182
945 119238759
946 122556346
947 120876700
948 124361620
949 122600123
950 125999423
951 124279769
952 127850047
953 126041266
954 129524351
955 127760920
956 131418515
957 129569701
958 133138406
959 131333132
960 135080153
961 133181946
962 136837844
963 134987220
964 138825065
965 136885427
966 140630215
967 138736051
968 142666668
969 140675689
970 144511600
971 142569853
972 146595337
973 144560832
974 148489800
975 146502579
976 150625144
977 148537084
978 152560758
979 150524305
980 154745495
981 152612365
982 156732555
983 154648818
984 158970705
985 156781948
986 161001029
987 158865685
988 163290520
989 161054442
990 165374523
991 163189786
992 167719974
993 165425864
994 169848751
995 167610601
996 172247757
997 169904711
998 174432352
999 172142861
1000 176889218