1 1
2 18
3 80
4 217
5 459
6 836
7 1378
8 2115
9 3077
10 4294
11 5796
12 7613
13 9775
14 12312
15 15254
16 18631
17 22473
18 26810
19 31672
20 37089
21 43091
22 49708
23 56970
24 64907
25 73549
26 82926
27 93068
28 104005
29 115767
30 128384
31 141886
32 156303
33 171665
34 188002
35 205344
36 223721
37 243163
38 263700
39 285362
40 308179
41 332181
42 357398
43 383860
44 411597
45 440639
46 471016
47 502758
48 535895
49 570457
50 606474
51 643976
52 682993
53 723555
54 765692
55 809434
56 854811
57 901853
58 950590
59 1001052
60 1053269
61 1107271
62 1163088
63 1220750
64 1280287
65 1341729
66 1405106
67 1470448
68 1537785
69 1607147
70 1678564
71 1752066
72 1827683
73 1905445
74 1985382
75 2067524
76 2151901
77 2238543
78 2327480
79 2418742
80 2512359
81 2608361
82 2706778
83 2807640
84 2910977
85 3016819
86 3125196
87 3236138
88 3349675
89 3465837
90 3584654
91 3706156
92 3830373
93 3957335
94 4087072
95 4219614
96 4354991
97 4493233
98 4634370
99 4778432
100 4925449
101 5075451
102 5228468
103 5384530
104 5543667
105 5705909
106 5871286
107 6039828
108 6211565
109 6386527
110 6564744
111 6746246
112 6931063
113 7119225
114 7310762
115 7505704
116 7704081
117 7905923
118 8111260
119 8320122
120 8532539
121 8748541
122 8968158
123 9191420
124 9418357
125 9648999
126 9883376
127 10121518
128 10363455
129 10609217
130 10858834
131 11112336
132 11369753
133 11631115
134 11896452
135 12165794
136 12439171
137 12716613
138 12998150
139 13283812
140 13573629
141 13867631
142 14165848
143 14468310
144 14775047
145 15086089
146 15401466
147 15721208
148 16045345
149 16373907
150 16706924
151 17044426
152 17386443
153 17733005
154 18084142
155 18439884
156 18800261
157 19165303
158 19535040
159 19909502
160 20288719
161 20672721
162 21061538
163 21455200
164 21853737
165 22257179
166 22665556
167 23078898
168 23497235
169 23920597
170 24349014
171 24782516
172 25221133
173 25664895
174 26113832
175 26567974
176 27027351
177 27491993
178 27961930
179 28437192
180 28917809
181 29403811
182 29895228
183 30392090
184 30894427
185 31402269
186 31915646
187 32434588
188 32959125
189 33489287
190 34025104
191 34566606
192 35113823
193 35666785
194 36225522
195 36790064
196 37360441
197 37936683
198 38518820
199 39106882
200 39700899
201 40300901
202 40906918
203 41518980
204 42137117
205 42761359
206 43391736
207 44028278
208 44671015
209 45319977
210 45975194
211 46636696
212 47304513
213 47978675
214 48659212
215 49346154
216 50039531
217 50739373
218 51445710
219 52158572
220 52877989
221 53603991
222 54336608
223 55075870
224 55821807
225 56574449
226 57333826
227 58099968
228 58872905
229 59652667
230 60439284
231 61232786
232 62033203
233 62840565
234 63654902
235 64476244
236 65304621
237 66140063
238 66982600
239 67832262
240 68689079
241 69553081
242 70424298
243 71302760
244 72188497
245 73081539
246 73981916
247 74889658
248 75804795
249 76727357
250 77657374
251 78594876
252 79539893
253 80492455
254 81452592
255 82420334
256 83395711
257 84378753
258 85369490
259 86367952
260 87374169
261 88388171
262 89409988
263 90439650
264 91477187
265 92522629
266 93576006
267 94637348
268 95706685
269 96784047
270 97869464
271 98962966
272 100064583
273 101174345
274 102292282
275 103418424
276 104552801
277 105695443
278 106846380
279 108005642
280 109173259
281 110349261
282 111533678
283 112726540
284 113927877
285 115137719
286 116356096
287 117583038
288 118818575
289 120062737
290 121315554
291 122577056
292 123847273
293 125126235
294 126413972
295 127710514
296 129015891
297 130330133
298 131653270
299 132985332
300 134326349
301 135676351
302 137035368
303 138403430
304 139780567
305 141166809
306 142562186
307 143966728
308 145380465
309 146803427
310 148235644
311 149677146
312 151127963
313 152588125
314 154057662
315 155536604
316 157024981
317 158522823
318 160030160
319 161547022
320 163073439
321 164609441
322 166155058
323 167710320
324 169275257
325 170849899
326 172434276
327 174028418
328 175632355
329 177246117
330 178869734
331 180503236
332 182146653
333 183800015
334 185463352
335 187136694
336 188820071
337 190513513
338 192217050
339 193930712
340 195654529
341 197388531
342 199132748
343 200887210
344 202651947
345 204426989
346 206212366
347 208008108
348 209814245
349 211630807
350 213457824
351 215295326
352 217143343
353 219001905
354 220871042
355 222750784
356 224641161
357 226542203
358 228453940
359 230376402
360 232309619
361 234253621
362 236208438
363 238174100
364 240150637
365 242138079
366 244136456
367 246145798
368 248166135
369 250197497
370 252239914
371 254293416
372 256358033
373 258433795
374 260520732
375 262618874
376 264728251
377 266848893
378 268980830
379 271124092
380 273278709
381 275444711
382 277622128
383 279810990
384 282011327
385 284223169
386 286446546
387 288681488
388 290928025
389 293186187
390 295456004
391 297737506
392 300030723
393 302335685
394 304652422
395 306980964
396 309321341
397 311673583
398 314037720
399 316413782
400 318801799
401 321201801
402 323613818
403 326037880
404 328474017
405 330922259
406 333382636
407 335855178
408 338339915
409 340836877
410 343346094
411 345867596
412 348401413
413 350947575
414 353506112
415 356077054
416 358660431
417 361256273
418 363864610
419 366485472
420 369118889
421 371764891
422 374423508
423 377094770
424 379778707
425 382475349
426 385184726
427 387906868
428 390641805
429 393389567
430 396150184
431 398923686
432 401710103
433 404509465
434 407321802
435 410147144
436 412985521
437 415836963
438 418701500
439 421579162
440 424469979
441 427373981
442 430291198
443 433221660
444 436165397
445 439122439
446 442092816
447 445076558
448 448073695
449 451084257
450 454108274
451 457145776
452 460196793
453 463261355
454 466339492
455 469431234
456 472536611
457 475655653
458 478788390
459 481934852
460 485095069
461 488269071
462 491456888
463 494658550
464 497874087
465 501103529
466 504346906
467 507604248
468 510875585
469 514160947
470 517460364
471 520773866
472 524101483
473 527443245
474 530799182
475 534169324
476 537553701
477 540952343
478 544365280
479 547792542
480 551234159
481 554690161
482 558160578
483 561645440
484 565144777
485 568658619
486 572186996
487 575729938
488 579287475
489 582859637
490 586446454
491 590047956
492 593664173
493 597295135
494 600940872
495 604601414
496 608276791
497 611967033
498 615672170
499 619392232
500 623127249
501 626877251
502 630642268
503 634422330
504 638217467
505 642027709
506 645853086
507 649693628
508 653549365
509 657420327
510 661306544
511 665208046
512 669124863
513 673057025
514 677004562
515 680967504
516 684945881
517 688939723
518 692949060
519 696973922
520 701014339
521 705070341
522 709141958
523 713229220
524 717332157
525 721450799
526 725585176
527 729735318
528 733901255
529 738083017
530 742280634
531 746494136
532 750723553
533 754968915
534 759230252
535 763507594
536 767800971
537 772110413
538 776435950
539 780777612
540 785135429
541 789509431
542 793899648
543 798306110
544 802728847
545 807167889
546 811623266
547 816095008
548 820583145
549 825087707
550 829608724
551 834146226
552 838700243
553 843270805
554 847857942
555 852461684
556 857082061
557 861719103
558 866372840
559 871043302
560 875730519
561 880434521
562 885155338
563 889893000
564 894647537
565 899418979
566 904207356
567 909012698
568 913835035
569 918674397
570 923530814
571 928404316
572 933294933
573 938202695
574 943127632
575 948069774
576 953029151
577 958005793
578 962999730
579 968010992
580 973039609
581 978085611
582 983149028
583 988229890
584 993328227
585 998444069
586 1003577446
587 1008728388
588 1013896925
589 1019083087
590 1024286904
591 1029508406
592 1034747623
593 1040004585
594 1045279322
595 1050571864
596 1055882241
597 1061210483
598 1066556620
599 1071920682
600 1077302699
601 1082702701
602 1088120718
603 1093556780
604 1099010917
605 1104483159
606 1109973536
607 1115482078
608 1121008815
609 1126553777
610 1132116994
611 1137698496
612 1143298313
613 1148916475
614 1154553012
615 1160207954
616 1165881331
617 1171573173
618 1177283510
619 1183012372
620 1188759789
621 1194525791
622 1200310408
623 1206113670
624 1211935607
625 1217776249
626 1223635626
627 1229513768
628 1235410705
629 1241326467
630 1247261084
631 1253214586
632 1259187003
633 1265178365
634 1271188702
635 1277218044
636 1283266421
637 1289333863
638 1295420400
639 1301526062
640 1307650879
641 1313794881
642 1319958098
643 1326140560
644 1332342297
645 1338563339
646 1344803716
647 1351063458
648 1357342595
649 1363641157
650 1369959174
651 1376296676
652 1382653693
653 1389030255
654 1395426392
655 1401842134
656 1408277511
657 1414732553
658 1421207290
659 1427701752
660 1434215969
661 1440749971
662 1447303788
663 1453877450
664 1460470987
665 1467084429
666 1473717806
667 1480371148
668 1487044485
669 1493737847
670 1500451264
671 1507184766
672 1513938383
673 1520712145
674 1527506082
675 1534320224
676 1541154601
677 1548009243
678 1554884180
679 1561779442
680 1568695059
681 1575631061
682 1582587478
683 1589564340
684 1596561677
685 1603579519
686 1610617896
687 1617676838
688 1624756375
689 1631856537
690 1638977354
691 1646118856
692 1653281073
693 1660464035
694 1667667772
695 1674892314
696 1682137691
697 1689403933
698 1696691070
699 1703999132
700 1711328149
701 1718678151
702 1726049168
703 1733441230
704 1740854367
705 1748288609
706 1755743986
707 1763220528
708 1770718265
709 1778237227
710 1785777444
711 1793338946
712 1800921763
713 1808525925
714 1816151462
715 1823798404
716 1831466781
717 1839156623
718 1846867960
719 1854600822
720 1862355239
721 1870131241
722 1877928858
723 1885748120
724 1893589057
725 1901451699
726 1909336076
727 1917242218
728 1925170155
729 1933119917
730 1941091534
731 1949085036
732 1957100453
733 1965137815
734 1973197152
735 1981278494
736 1989381871
737 1997507313
738 2005654850
739 2013824512
740 2022016329
741 2030230331
742 2038466548
743 2046725010
744 2055005747
745 2063308789
746 2071634166
747 2079981908
748 2088352045
749 2096744607
750 2105159624
751 2113597126
752 2122057143
753 2130539705
754 2139044842
755 2147572584
756 2156122961
757 2164696003
758 2173291740
759 2181910202
760 2190551419
761 2199215421
762 2207902238
763 2216611900
764 2225344437
765 2234099879
766 2242878256
767 2251679598
768 2260503935
769 2269351297
770 2278221714
771 2287115216
772 2296031833
773 2304971595
774 2313934532
775 2322920674
776 2331930051
777 2340962693
778 2350018630
779 2359097892
780 2368200509
781 2377326511
782 2386475928
783 2395648790
784 2404845127
785 2414064969
786 2423308346
787 2432575288
788 2441865825
789 2451179987
790 2460517804
791 2469879306
792 2479264523
793 2488673485
794 2498106222
795 2507562764
796 2517043141
797 2526547383
798 2536075520
799 2545627582
800 2555203599
801 2564803601
802 2574427618
803 2584075680
804 2593747817
805 2603444059
806 2613164436
807 2622908978
808 2632677715
809 2642470677
810 2652287894
811 2662129396
812 2671995213
813 2681885375
814 2691799912
815 2701738854
816 2711702231
817 2721690073
818 2731702410
819 2741739272
820 2751800689
821 2761886691
822 2771997308
823 2782132570
824 2792292507
825 2802477149
826 2812686526
827 2822920668
828 2833179605
829 2843463367
830 2853771984
831 2864105486
832 2874463903
833 2884847265
834 2895255602
835 2905688944
836 2916147321
837 2926630763
838 2937139300
839 2947672962
840 2958231779
841 2968815781
842 2979424998
843 2990059460
844 3000719197
845 3011404239
846 3022114616
847 3032850358
848 3043611495
849 3054398057
850 3065210074
851 3076047576
852 3086910593
853 3097799155
854 3108713292
855 3119653034
856 3130618411
857 3141609453
858 3152626190
859 3163668652
860 3174736869
861 3185830871
862 3196950688
863 3208096350
864 3219267887
865 3230465329
866 3241688706
867 3252938048
868 3264213385
869 3275514747
870 3286842164
871 3298195666
872 3309575283
873 3320981045
874 3332412982
875 3343871124
876 3355355501
877 3366866143
878 3378403080
879 3389966342
880 3401555959
881 3413171961
882 3424814378
883 3436483240
884 3448178577
885 3459900419
886 3471648796
887 3483423738
888 3495225275
889 3507053437
890 3518908254
891 3530789756
892 3542697973
893 3554632935
894 3566594672
895 3578583214
896 3590598591
897 3602640833
898 3614709970
899 3626806032
900 3638929049
901 3651079051
902 3663256068
903 3675460130
904 3687691267
905 3699949509
906 3712234886
907 3724547428
908 3736887165
909 3749254127
910 3761648344
911 3774069846
912 3786518663
913 3798994825
914 3811498362
915 3824029304
916 3836587681
917 3849173523
918 3861786860
919 3874427722
920 3887096139
921 3899792141
922 3912515758
923 3925267020
924 3938045957
925 3950852599
926 3963686976
927 3976549118
928 3989439055
929 4002356817
930 4015302434
931 4028275936
932 4041277353
933 4054306715
934 4067364052
935 4080449394
936 4093562771
937 4106704213
938 4119873750
939 4133071412
940 4146297229
941 4159551231
942 4172833448
943 4186143910
944 4199482647
945 4212849689
946 4226245066
947 4239668808
948 4253120945
949 4266601507
950 4280110524
951 4293648026
952 4307214043
953 4320808605
954 4334431742
955 4348083484
956 4361763861
957 4375472903
958 4389210640
959 4402977102
960 4416772319
961 4430596321
962 4444449138
963 4458330800
964 4472241337
965 4486180779
966 4500149156
967 4514146498
968 4528172835
969 4542228197
970 4556312614
971 4570426116
972 4584568733
973 4598740495
974 4612941432
975 4627171574
976 4641430951
977 4655719593
978 4670037530
979 4684384792
980 4698761409
981 4713167411
982 4727602828
983 4742067690
984 4756562027
985 4771085869
986 4785639246
987 4800222188
988 4814834725
989 4829476887
990 4844148704
991 4858850206
992 4873581423
993 4888342385
994 4903133122
995 4917953664
996 4932804041
997 4947684283
998 4962594420
999 4977534482
1000 4992504499