1 1
2 12
3 50
4 133
5 279
6 506
7 832
8 1275
9 1853
10 2584
11 3486
12 4577
13 5875
14 7398
15 9164
16 11191
17 13497
18 16100
19 19018
20 22269
21 25871
22 29842
23 34200
24 38963
25 44149
26 49776
27 55862
28 62425
29 69483
30 77054
31 85156
32 93807
33 103025
34 112828
35 123234
36 134261
37 145927
38 158250
39 171248
40 184939
41 199341
42 214472
43 230350
44 246993
45 264419
46 282646
47 301692
48 321575
49 342313
50 363924
51 386426
52 409837
53 434175
54 459458
55 485704
56 512931
57 541157
58 570400
59 600678
60 632009
61 664411
62 697902
63 732500
64 768223
65 805089
66 843116
67 882322
68 922725
69 964343
70 1007194
71 1051296
72 1096667
73 1143325
74 1191288
75 1240574
76 1291201
77 1343187
78 1396550
79 1451308
80 1507479
81 1565081
82 1624132
83 1684650
84 1746653
85 1810159
86 1875186
87 1941752
88 2009875
89 2079573
90 2150864
91 2223766
92 2298297
93 2374475
94 2452318
95 2531844
96 2613071
97 2696017
98 2780700
99 2867138
100 2955349
101 3045351
102 3137162
103 3230800
104 3326283
105 3423629
106 3522856
107 3623982
108 3727025
109 3832003
110 3938934
111 4047836
112 4158727
113 4271625
114 4386548
115 4503514
116 4622541
117 4743647
118 4866850
119 4992168
120 5119619
121 5249221
122 5380992
123 5514950
124 5651113
125 5789499
126 5930126
127 6073012
128 6218175
129 6365633
130 6515404
131 6667506
132 6821957
133 6978775
134 7137978
135 7299584
136 7463611
137 7630077
138 7799000
139 7970398
140 8144289
141 8320691
142 8499622
143 8681100
144 8865143
145 9051769
146 9240996
147 9432842
148 9627325
149 9824463
150 10024274
151 10226776
152 10431987
153 10639925
154 10850608
155 11064054
156 11280281
157 11499307
158 11721150
159 11945828
160 12173359
161 12403761
162 12637052
163 12873250
164 13112373
165 13354439
166 13599466
167 13847472
168 14098475
169 14352493
170 14609544
171 14869646
172 15132817
173 15399075
174 15668438
175 15940924
176 16216551
177 16495337
178 16777300
179 17062458
180 17350829
181 17642431
182 17937282
183 18235400
184 18536803
185 18841509
186 19149536
187 19460902
188 19775625
189 20093723
190 20415214
191 20740116
192 21068447
193 21400225
194 21735468
195 22074194
196 22416421
197 22762167
198 23111450
199 23464288
200 23820699
201 24180701
202 24544312
203 24911550
204 25282433
205 25656979
206 26035206
207 26417132
208 26802775
209 27192153
210 27585284
211 27982186
212 28382877
213 28787375
214 29195698
215 29607864
216 30023891
217 30443797
218 30867600
219 31295318
220 31726969
221 32162571
222 32602142
223 33045700
224 33493263
225 33944849
226 34400476
227 34860162
228 35323925
229 35791783
230 36263754
231 36739856
232 37220107
233 37704525
234 38193128
235 38685934
236 39182961
237 39684227
238 40189750
239 40699548
240 41213639
241 41732041
242 42254772
243 42781850
244 43313293
245 43849119
246 44389346
247 44933992
248 45483075
249 46036613
250 46594624
251 47157126
252 47724137
253 48295675
254 48871758
255 49452404
256 50037631
257 50627457
258 51221900
259 51820978
260 52424709
261 53033111
262 53646202
263 54264000
264 54886523
265 55513789
266 56145816
267 56782622
268 57424225
269 58070643
270 58721894
271 59377996
272 60038967
273 60704825
274 61375588
275 62051274
276 62731901
277 63417487
278 64108050
279 64803608
280 65504179
281 66209781
282 66920432
283 67636150
284 68356953
285 69082859
286 69813886
287 70550052
288 71291375
289 72037873
290 72789564
291 73546466
292 74308597
293 75075975
294 75848618
295 76626544
296 77409771
297 78198317
298 78992200
299 79791438
300 80596049
301 81406051
302 82221462
303 83042300
304 83868583
305 84700329
306 85537556
307 86380282
308 87228525
309 88082303
310 88941634
311 89806536
312 90677027
313 91553125
314 92434848
315 93322214
316 94215241
317 95113947
318 96018350
319 96928468
320 97844319
321 98765921
322 99693292
323 100626450
324 101565413
325 102510199
326 103460826
327 104417312
328 105379675
329 106347933
330 107322104
331 108302206
332 109288257
333 110280275
334 111278278
335 112282284
336 113292311
337 114308377
338 115330500
339 116358698
340 117392989
341 118433391
342 119479922
343 120532600
344 121591443
345 122656469
346 123727696
347 124805142
348 125888825
349 126978763
350 128074974
351 129177476
352 130286287
353 131401425
354 132522908
355 133650754
356 134784981
357 135925607
358 137072650
359 138226128
360 139386059
361 140552461
362 141725352
363 142904750
364 144090673
365 145283139
366 146482166
367 147687772
368 148899975
369 150118793
370 151344244
371 152576346
372 153815117
373 155060575
374 156312738
375 157571624
376 158837251
377 160109637
378 161388800
379 162674758
380 163967529
381 165267131
382 166573582
383 167886900
384 169207103
385 170534209
386 171868236
387 173209202
388 174557125
389 175912023
390 177273914
391 178642816
392 180018747
393 181401725
394 182791768
395 184188894
396 185593121
397 187004467
398 188422950
399 189848588
400 191281399
401 192721401
402 194168612
403 195623050
404 197084733
405 198553679
406 200029906
407 201513432
408 203004275
409 204502453
410 206007984
411 207520886
412 209041177
413 210568875
414 212103998
415 213646564
416 215196591
417 216754097
418 218319100
419 219891618
420 221471669
421 223059271
422 224654442
423 226257200
424 227867563
425 229485549
426 231111176
427 232744462
428 234385425
429 236034083
430 237690454
431 239354556
432 241026407
433 242706025
434 244393428
435 246088634
436 247791661
437 249502527
438 251221250
439 252947848
440 254682339
441 256424741
442 258175072
443 259933350
444 261699593
445 263473819
446 265256046
447 267046292
448 268844575
449 270650913
450 272465324
451 274287826
452 276118437
453 277957175
454 279804058
455 281659104
456 283522331
457 285393757
458 287273400
459 289161278
460 291057409
461 292961811
462 294874502
463 296795500
464 298724823
465 300662489
466 302608516
467 304562922
468 306525725
469 308496943
470 310476594
471 312464696
472 314461267
473 316466325
474 318479888
475 320501974
476 322532601
477 324571787
478 326619550
479 328675908
480 330740879
481 332814481
482 334896732
483 336987650
484 339087253
485 341195559
486 343312586
487 345438352
488 347572875
489 349716173
490 351868264
491 354029166
492 356198897
493 358377475
494 360564918
495 362761244
496 364966471
497 367180617
498 369403700
499 371635738
500 373876749
501 376126751
502 378385762
503 380653800
504 382930883
505 385217029
506 387512256
507 389816582
508 392130025
509 394452603
510 396784334
511 399125236
512 401475327
513 403834625
514 406203148
515 408580914
516 410967941
517 413364247
518 415769850
519 418184768
520 420609019
521 423042621
522 425485592
523 427937950
524 430399713
525 432870899
526 435351526
527 437841612
528 440341175
529 442850233
530 445368804
531 447896906
532 450434557
533 452981775
534 455538578
535 458104984
536 460681011
537 463266677
538 465862000
539 468466998
540 471081689
541 473706091
542 476340222
543 478984100
544 481637743
545 484301169
546 486974396
547 489657442
548 492350325
549 495053063
550 497765674
551 500488176
552 503220587
553 505962925
554 508715208
555 511477454
556 514249681
557 517031907
558 519824150
559 522626428
560 525438759
561 528261161
562 531093652
563 533936250
564 536788973
565 539651839
566 542524866
567 545408072
568 548301475
569 551205093
570 554118944
571 557043046
572 559977417
573 562922075
574 565877038
575 568842324
576 571817951
577 574803937
578 577800300
579 580807058
580 583824229
581 586851831
582 589889882
583 592938400
584 595997403
585 599066909
586 602146936
587 605237502
588 608338625
589 611450323
590 614572614
591 617705516
592 620849047
593 624003225
594 627168068
595 630343594
596 633529821
597 636726767
598 639934450
599 643152888
600 646382099
601 649622101
602 652872912
603 656134550
604 659407033
605 662690379
606 665984606
607 669289732
608 672605775
609 675932753
610 679270684
611 682619586
612 685979477
613 689350375
614 692732298
615 696125264
616 699529291
617 702944397
618 706370600
619 709807918
620 713256369
621 716715971
622 720186742
623 723668700
624 727161863
625 730666249
626 734181876
627 737708762
628 741246925
629 744796383
630 748357154
631 751929256
632 755512707
633 759107525
634 762713728
635 766331334
636 769960361
637 773600827
638 777252750
639 780916148
640 784591039
641 788277441
642 791975372
643 795684850
644 799405893
645 803138519
646 806882746
647 810638592
648 814406075
649 818185213
650 821976024
651 825778526
652 829592737
653 833418675
654 837256358
655 841105804
656 844967031
657 848840057
658 852724900
659 856621578
660 860530109
661 864450511
662 868382802
663 872327000
664 876283123
665 880251189
666 884231216
667 888223222
668 892227225
669 896243243
670 900271294
671 904311396
672 908363567
673 912427825
674 916504188
675 920592674
676 924693301
677 928806087
678 932931050
679 937068208
680 941217579
681 945379181
682 949553032
683 953739150
684 957937553
685 962148259
686 966371286
687 970606652
688 974854375
689 979114473
690 983386964
691 987671866
692 991969197
693 996278975
694 1000601218
695 1004935944
696 1009283171
697 1013642917
698 1018015200
699 1022400038
700 1026797449
701 1031207451
702 1035630062
703 1040065300
704 1044513183
705 1048973729
706 1053446956
707 1057932882
708 1062431525
709 1066942903
710 1071467034
711 1076003936
712 1080553627
713 1085116125
714 1089691448
715 1094279614
716 1098880641
717 1103494547
718 1108121350
719 1112761068
720 1117413719
721 1122079321
722 1126757892
723 1131449450
724 1136154013
725 1140871599
726 1145602226
727 1150345912
728 1155102675
729 1159872533
730 1164655504
731 1169451606
732 1174260857
733 1179083275
734 1183918878
735 1188767684
736 1193629711
737 1198504977
738 1203393500
739 1208295298
740 1213210389
741 1218138791
742 1223080522
743 1228035600
744 1233004043
745 1237985869
746 1242981096
747 1247989742
748 1253011825
749 1258047363
750 1263096374
751 1268158876
752 1273234887
753 1278324425
754 1283427508
755 1288544154
756 1293674381
757 1298818207
758 1303975650
759 1309146728
760 1314331459
761 1319529861
762 1324741952
763 1329967750
764 1335207273
765 1340460539
766 1345727566
767 1351008372
768 1356302975
769 1361611393
770 1366933644
771 1372269746
772 1377619717
773 1382983575
774 1388361338
775 1393753024
776 1399158651
777 1404578237
778 1410011800
779 1415459358
780 1420920929
781 1426396531
782 1431886182
783 1437389900
784 1442907703
785 1448439609
786 1453985636
787 1459545802
788 1465120125
789 1470708623
790 1476311314
791 1481928216
792 1487559347
793 1493204725
794 1498864368
795 1504538294
796 1510226521
797 1515929067
798 1521645950
799 1527377188
800 1533122799
801 1538882801
802 1544657212
803 1550446050
804 1556249333
805 1562067079
806 1567899306
807 1573746032
808 1579607275
809 1585483053
810 1591373384
811 1597278286
812 1603197777
813 1609131875
814 1615080598
815 1621043964
816 1627021991
817 1633014697
818 1639022100
819 1645044218
820 1651081069
821 1657132671
822 1663199042
823 1669280200
824 1675376163
825 1681486949
826 1687612576
827 1693753062
828 1699908425
829 1706078683
830 1712263854
831 1718463956
832 1724679007
833 1730909025
834 1737154028
835 1743414034
836 1749689061
837 1755979127
838 1762284250
839 1768604448
840 1774939739
841 1781290141
842 1787655672
843 1794036350
844 1800432193
845 1806843219
846 1813269446
847 1819710892
848 1826167575
849 1832639513
850 1839126724
851 1845629226
852 1852147037
853 1858680175
854 1865228658
855 1871792504
856 1878371731
857 1884966357
858 1891576400
859 1898201878
860 1904842809
861 1911499211
862 1918171102
863 1924858500
864 1931561423
865 1938279889
866 1945013916
867 1951763522
868 1958528725
869 1965309543
870 1972105994
871 1978918096
872 1985745867
873 1992589325
874 1999448488
875 2006323374
876 2013214001
877 2020120387
878 2027042550
879 2033980508
880 2040934279
881 2047903881
882 2054889332
883 2061890650
884 2068907853
885 2075940959
886 2082989986
887 2090054952
888 2097135875
889 2104232773
890 2111345664
891 2118474566
892 2125619497
893 2132780475
894 2139957518
895 2147150644
896 2154359871
897 2161585217
898 2168826700
899 2176084338
900 2183358149
901 2190648151
902 2197954362
903 2205276800
904 2212615483
905 2219970429
906 2227341656
907 2234729182
908 2242133025
909 2249553203
910 2256989734
911 2264442636
912 2271911927
913 2279397625
914 2286899748
915 2294418314
916 2301953341
917 2309504847
918 2317072850
919 2324657368
920 2332258419
921 2339876021
922 2347510192
923 2355160950
924 2362828313
925 2370512299
926 2378212926
927 2385930212
928 2393664175
929 2401414833
930 2409182204
931 2416966306
932 2424767157
933 2432584775
934 2440419178
935 2448270384
936 2456138411
937 2464023277
938 2471925000
939 2479843598
940 2487779089
941 2495731491
942 2503700822
943 2511687100
944 2519690343
945 2527710569
946 2535747796
947 2543802042
948 2551873325
949 2559961663
950 2568067074
951 2576189576
952 2584329187
953 2592485925
954 2600659808
955 2608850854
956 2617059081
957 2625284507
958 2633527150
959 2641787028
960 2650064159
961 2658358561
962 2666670252
963 2674999250
964 2683345573
965 2691709239
966 2700090266
967 2708488672
968 2716904475
969 2725337693
970 2733788344
971 2742256446
972 2750742017
973 2759245075
974 2767765638
975 2776303724
976 2784859351
977 2793432537
978 2802023300
979 2810631658
980 2819257629
981 2827901231
982 2836562482
983 2845241400
984 2853938003
985 2862652309
986 2871384336
987 2880134102
988 2888901625
989 2897686923
990 2906490014
991 2915310916
992 2924149647
993 2933006225
994 2941880668
995 2950772994
996 2959683221
997 2968611367
998 2977557450
999 2986521488
1000 2995503499