0 1
1 4
2 10
3 20
4 36
5 56
6 76
7 105
8 144
9 180
10 215
11 260
12 323
13 374
14 413
15 484
16 573
17 637
18 690
19 779
20 895
21 967
22 1021
23 1143
24 1289
25 1369
26 1434
27 1577
28 1755
29 1841
30 1898
31 2079
32 2292
33 2383
34 2449
35 2652
36 2900
37 2992
38 3047
39 3294
40 3580
41 3672
42 3735
43 4007
44 4332
45 4422
46 4465
47 4788
48 5156
49 5242
50 5290
51 5639
52 6051
53 6130
54 6154
55 6559
56 7017
57 7089
58 7117
59 7550
60 8055
61 8117
62 8114
63 8610
64 9165
65 9215
66 9213
67 9740
68 10347
69 10381
70 10343
71 10938
72 11600
73 11619
74 11580
75 12207
76 12924
77 12926
78 12844
79 13545
80 14320
81 14302
82 14218
83 14954
84 15788
85 15746
86 15614
87 16431
88 17328
89 17262
90 17125
91 17978
92 18939
93 18848
94 18655
95 19594
96 20621
97 20503
98 20304
99 21281
100 22375
101 22225
102 21967
103 23037
104 24201
105 24019
106 23752
107 24863
108 26099
109 25883
110 25548
111 26757
112 28068
113 27817
114 27471
115 28722
116 30108
117 29818
118 29401
119 30756
120 32220
121 31890
122 31461
123 32861
124 34404
125 34032
126 33523
127 35034
128 36660
129 36244
130 35720
131 37277
132 38987
133 38524
134 37916
135 39589
136 41385
137 40875
138 40251
139 41972
140 43855
141 43295
142 42580
143 44424
144 46397
145 45785
146 45051
147 46946
148 49011
149 48343
150 47513
151 49536
152 51696
153 50973
154 50122
155 52197
156 54452
157 53672
158 52718
159 54927
160 57280
161 56440
162 55464
163 57728
164 60180
165 59276
166 58192
167 60597
168 63152
169 62184
170 61075
171 63536
172 66195
173 65162
174 63937
175 66544
176 69309
177 68209
178 66958
179 69623
180 72495
181 71323
182 69953
183 72771
184 75753
185 74509
186 73110
187 75989
188 79083
189 77765
190 76238
191 79275
192 82484
193 81091
194 79533
195 82632
196 85956
197 84484
198 82795
199 86058
200 89500
201 87948
202 86227
203 89555
204 93116
205 91482
206 89621
207 93120
208 96804
209 95086
210 93190
211 96755
212 100563
213 98758
214 96718
215 100459
216 104393
217 102501
218 100425
219 104234
220 108295
221 106313
222 104086
223 108078
224 112269
225 110195
226 107929
227 111992
228 116315
229 114145
230 111723
231 115974
232 120432
233 118167
234 115704
235 120027
236 124620
237 122258
238 119632
239 124149
240 128880
241 126418
242 123750
243 128342
244 133212
245 130646
246 127810
247 132603
248 137616
249 134946
250 132065
251 136934
252 142091
253 139316
254 136259
255 141334
256 146637
257 143755
258 140652
259 145805
260 151255
261 148261
262 144979
263 150345
264 155945
265 152839
266 149508
267 154955
268 160707
269 157487
270 153968
271 159633
272 165540
273 162205
274 158635
275 164382
276 170444
277 166990
278 163229
279 169200
280 175420
281 171846
282 168033
283 174089
284 180468
285 176772
286 172759
287 179046
288 185588
289 181768
290 177700
291 184073
292 190779
293 186832
294 182560
295 189169
296 196041
297 191967
298 187639
299 194336
300 201375
301 197171
302 192632
303 199572
304 206781
305 202445
306 197847
307 204878
308 212259
309 207787
310 202973
311 210252
312 217808
313 213201
314 208326
315 215697
316 223428
317 218684
318 213586
319 221211
320 229120
321 224236
322 219076
323 226796
324 234884
325 229856
326 224468
327 232449
328 240720
329 235548
330 230095
331 238172
332 246627
333 241310
334 235621
335 243964
336 252605
337 247141
338 241386
339 249827
340 258655
341 253039
342 247045
343 255759
344 264777
345 259009
346 252946
347 261761
348 270971
349 265049
350 258738
351 267831
352 277236
353 271159
354 264777
355 273972
356 283572
357 277336
358 270703
359 280182
360 289980
361 283584
362 276879
363 286463
364 296460
365 289902
366 282937
367 292812
368 303012
369 296290
370 289250
371 299231
372 309635
373 302746
374 295442
375 305719
376 316329
377 309273
378 301893
379 312278
380 323095
381 315869
382 308218
383 318906
384 329933
385 322535
386 314805
387 325604
388 336843
389 329269
390 321263
391 332370
392 343824
393 336075
394 327988
395 339207
396 350876
397 342950
398 334580
399 346113
400 358000
401 349894
402 341442
403 353090
404 365196
405 356906
406 348166
407 360135
408 372464
409 363990
410 355165
411 367250
412 379803
413 371144
414 362023
415 374434
416 387213
417 378367
418 369160
419 381689
420 394695
421 385657
422 376151
423 389013
424 402249
425 393019
426 383424
427 396407
428 409875
429 400451
430 390548
431 403869
432 417572
433 407953
434 397959
435 411402
436 425340
437 415522
438 405217
439 419004
440 433180
441 423162
442 412765
443 426677
444 441092
445 430872
446 420155
447 434418
448 449076
449 438652
450 427840
451 442229
452 457131
453 446500
454 435364
455 450109
456 465257
457 454419
458 443187
459 458060
460 473455
461 462407
462 450844
463 466080
464 481725
465 470465
466 458803
467 474170
468 490067
469 478591
470 466593
471 482328
472 498480
473 486789
474 474690
475 490557
476 506964
477 495056
478 482614
479 498855
480 515520
481 503392
482 490848
483 507224
484 524148
485 511796
486 498904
487 515661
488 532848
489 520272
490 507275
491 524168
492 541619
493 528818
494 515465
495 532744
496 550461
497 537433
498 523974
499 541391
500 559375
501 546115
502 532297
503 550107
504 568361
505 554869
506 540942
507 558893
508 577419
509 563693
510 549398
511 567747
512 586548
513 572587
514 558181
515 576672
516 595748
517 581548
518 566771
519 585666
520 605020
521 590580
522 575691
523 594731
524 614364
525 599682
526 584413
527 603864
528 623780
529 608854
530 593470
531 613067
532 633267
533 618094
534 602326
535 622339
536 642825
537 627405
538 611521
539 631682
540 652455
541 636785
542 620510
543 641094
544 662157
545 646235
546 629841
547 650576
548 671931
549 655753
550 638963
551 660126
552 681776
553 665343
554 648432
555 669747
556 691692
557 675002
558 657688
559 679437
560 701680
561 684730
562 667294
563 689198
564 711740
565 694526
566 676682
567 699027
568 721872
569 704394
570 686425
571 708926
572 732075
573 714332
574 695947
575 718894
576 742349
577 724339
578 705828
579 728933
580 752695
581 734413
582 715483
583 739041
584 763113
585 744559
586 725500
587 749219
588 773603
589 754775
590 735288
591 759465
592 784164
593 765061
594 745443
595 769782
596 794796
597 775414
598 755365
599 780168
600 805500
601 785838
602 765657
603 790625
604 816276
605 796332
606 775711
607 801150
608 827124
609 806896
610 786140
611 811745
612 838043
613 817528
614 796328
615 822409
616 849033
617 828231
618 806895
619 833144
620 860095
621 839003
622 817216
623 843948
624 871229
625 849845
626 827919
627 854822
628 882435
629 860755
630 838373
631 865764
632 893712
633 871737
634 849214
635 876777
636 905060
637 882788
638 859802
639 887859
640 916480
641 893908
642 870780
643 899012
644 927972
645 905096
646 881500
647 910233
648 939536
649 916356
650 892615
651 921524
652 951171
653 927686
654 903469
655 932884
656 962877
657 939085
658 914722
659 944315
660 974655
661 950551
662 925709
663 955815
664 986505
665 962089
666 937098
667 967385
668 998427
669 973697
670 948218
671 979023
672 1010420
673 985375
674 959745
675 990732
676 1022484
677 997120
678 970999
679 1002510
680 1034620
681 1008936
682 982663
683 1014359
684 1046828
685 1020822
686 994049
687 1026276
688 1059108
689 1032778
690 1005850
691 1038263
692 1071459
693 1044802
694 1017370
695 1050319
696 1083881
697 1056897
698 1029309
699 1062446
700 1096375
701 1069061
702 1040962
703 1074642
704 1108941
705 1081295
706 1053037
707 1086908
708 1121579
709 1093597
710 1064823
711 1099242
712 1134288
713 1105971
714 1077036
715 1111647
716 1147068
717 1118414
718 1088956
719 1124121
720 1159920
721 1130926
722 1101306
723 1136666
724 1172844
725 1143506
726 1113358
727 1149279
728 1185840
729 1156158
730 1125845
731 1161962
732 1198907
733 1168880
734 1138031
735 1174714
736 1212045
737 1181671
738 1150656
739 1187537
740 1225255
741 1194529
742 1162975
743 1200429
744 1238537
745 1207459
746 1175736
747 1213391
748 1251891
749 1220459
750 1188188
751 1226421
752 1265316
753 1233529
754 1201087
755 1239522
756 1278812
757 1246666
758 1213673
759 1252692
760 1292380
761 1259874
762 1226709
763 1265933
764 1306020
765 1273152
766 1239427
767 1279242
768 1319732
769 1286500
770 1252600
771 1292621
772 1333515
773 1299916
774 1265452
775 1306069
776 1347369
777 1313403
778 1278763
779 1319588
780 1361295
781 1326959
782 1291748
783 1333176
784 1375293
785 1340585
786 1305195
787 1346834
788 1389363
789 1354279
790 1318313
791 1360560
792 1403504
793 1368045
794 1331898
795 1374357
796 1417716
797 1381880
798 1345150
799 1388223
800 1432000
801 1395784
802 1358872
803 1402160
804 1446356
805 1409756
806 1372256
807 1416165
808 1460784
809 1423800
810 1386115
811 1430240
812 1475283
813 1437914
814 1399633
815 1444384
816 1489853
817 1452097
818 1413630
819 1458599
820 1504495
821 1466347
822 1427281
823 1472883
824 1519209
825 1480669
826 1441414
827 1487237
828 1533995
829 1495061
830 1455198
831 1501659
832 1548852
833 1509523
834 1469469
835 1516152
836 1563780
837 1524052
838 1483387
839 1530714
840 1578780
841 1538652
842 1497795
843 1545347
844 1593852
845 1553322
846 1511845
847 1560048
848 1608996
849 1568062
850 1526390
851 1574819
852 1624211
853 1582870
854 1540574
855 1589659
856 1639497
857 1597749
858 1555257
859 1604570
860 1654855
861 1612697
862 1569574
863 1619550
864 1670285
865 1627715
866 1584393
867 1634600
868 1685787
869 1642801
870 1598843
871 1649718
872 1701360
873 1657959
874 1613800
875 1664907
876 1717004
877 1673186
878 1628384
879 1680165
880 1732720
881 1688482
882 1643478
883 1695494
884 1748508
885 1703846
886 1658194
887 1710891
888 1764368
889 1719282
890 1673425
891 1726358
892 1780299
893 1734788
894 1688275
895 1741894
896 1796301
897 1750363
898 1703644
899 1757501
900 1812375
901 1766005
902 1718627
903 1773177
904 1828521
905 1781719
906 1734132
907 1788923
908 1844739
909 1797503
910 1749248
911 1804737
912 1861028
913 1813357
914 1764891
915 1820622
916 1877388
917 1829278
918 1780141
919 1836576
920 1893820
921 1845270
922 1795921
923 1852601
924 1910324
925 1861332
926 1811303
927 1868694
928 1926900
929 1877464
930 1827220
931 1884857
932 1943547
933 1893664
934 1842736
935 1901089
936 1960265
937 1909935
938 1858791
939 1917392
940 1977055
941 1926275
942 1874440
943 1933764
944 1993917
945 1942685
946 1890631
947 1950206
948 2010851
949 1959163
950 1906413
951 1966716
952 2027856
953 1975713
954 1922742
955 1983297
956 2044932
957 1992332
958 1938658
959 1999947
960 2062080
961 2009020
962 1955124
963 2016668
964 2079300
965 2025776
966 1971172
967 2033457
968 2096592
969 2042604
970 1987775
971 2050316
972 2113955
973 2059502
974 2003957
975 2067244
976 2131389
977 2076469
978 2020698
979 2084243
980 2148895
981 2093503
982 2037013
983 2101311
984 2166473
985 2110609
986 2053890
987 2118449
988 2184123
989 2127785
990 2070338
991 2135655
992 2201844
993 2145031
994 2087353
995 2152932
996 2219636
997 2162344
998 2103935
999 2170278
1000 2237500