0 0
1 4
2 35
3 117
4 274
5 530
6 909
7 1435
8 2132
9 3024
10 4135
11 5489
12 7110
13 9022
14 11249
15 13815
16 16744
17 20060
18 23787
19 27949
20 32570
21 37674
22 43285
23 49427
24 56124
25 63400
26 71279
27 79785
28 88942
29 98774
30 109305
31 120559
32 132560
33 145332
34 158899
35 173285
36 188514
37 204610
38 221597
39 239499
40 258340
41 278144
42 298935
43 320737
44 343574
45 367470
46 392449
47 418535
48 445752
49 474124
50 503675
51 534429
52 566410
53 599642
54 634149
55 669955
56 707084
57 745560
58 785407
59 826649
60 869310
61 913414
62 958985
63 1006047
64 1054624
65 1104740
66 1156419
67 1209685
68 1264562
69 1321074
70 1379245
71 1439099
72 1500660
73 1563952
74 1628999
75 1695825
76 1764454
77 1834910
78 1907217
79 1981399
80 2057480
81 2135484
82 2215435
83 2297357
84 2381274
85 2467210
86 2555189
87 2645235
88 2737372
89 2831624
90 2928015
91 3026569
92 3127310
93 3230262
94 3335449
95 3442895
96 3552624
97 3664660
98 3779027
99 3895749
100 4014850
101 4136354
102 4260285
103 4386667
104 4515524
105 4646880
106 4780759
107 4917185
108 5056182
109 5197774
110 5341985
111 5488839
112 5638360
113 5790572
114 5945499
115 6103165
116 6263594
117 6426810
118 6592837
119 6761699
120 6933420
121 7108024
122 7285535
123 7465977
124 7649374
125 7835750
126 8025129
127 8217535
128 8412992
129 8611524
130 8813155
131 9017909
132 9225810
133 9436882
134 9651149
135 9868635
136 10089364
137 10313360
138 10540647
139 10771249
140 11005190
141 11242494
142 11483185
143 11727287
144 11974824
145 12225820
146 12480299
147 12738285
148 12999802
149 13264874
150 13533525
151 13805779
152 14081660
153 14361192
154 14644399
155 14931305
156 15221934
157 15516310
158 15814457
159 16116399
160 16422160
161 16731764
162 17045235
163 17362597
164 17683874
165 18009090
166 18338269
167 18671435
168 19008612
169 19349824
170 19695095
171 20044449
172 20397910
173 20755502
174 21117249
175 21483175
176 21853304
177 22227660
178 22606267
179 22989149
180 23376330
181 23767834
182 24163685
183 24563907
184 24968524
185 25377560
186 25791039
187 26208985
188 26631422
189 27058374
190 27489865
191 27925919
192 28366560
193 28811812
194 29261699
195 29716245
196 30175474
197 30639410
198 31108077
199 31581499
200 32059700
201 32542704
202 33030535
203 33523217
204 34020774
205 34523230
206 35030609
207 35542935
208 36060232
209 36582524
210 37109835
211 37642189
212 38179610
213 38722122
214 39269749
215 39822515
216 40380444
217 40943560
218 41511887
219 42085449
220 42664270
221 43248374
222 43837785
223 44432527
224 45032624
225 45638100
226 46248979
227 46865285
228 47487042
229 48114274
230 48747005
231 49385259
232 50029060
233 50678432
234 51333399
235 51993985
236 52660214
237 53332110
238 54009697
239 54692999
240 55382040
241 56076844
242 56777435
243 57483837
244 58196074
245 58914170
246 59638149
247 60368035
248 61103852
249 61845624
250 62593375
251 63347129
252 64106910
253 64872742
254 65644649
255 66422655
256 67206784
257 67997060
258 68793507
259 69596149
260 70405010
261 71220114
262 72041485
263 72869147
264 73703124
265 74543440
266 75390119
267 76243185
268 77102662
269 77968574
270 78840945
271 79719799
272 80605160
273 81497052
274 82395499
275 83300525
276 84212154
277 85130410
278 86055317
279 86986899
280 87925180
281 88870184
282 89821935
283 90780457
284 91745774
285 92717910
286 93696889
287 94682735
288 95675472
289 96675124
290 97681715
291 98695269
292 99715810
293 100743362
294 101777949
295 102819595
296 103868324
297 104924160
298 105987127
299 107057249
300 108134550
301 109219054
302 110310785
303 111409767
304 112516024
305 113629580
306 114750459
307 115878685
308 117014282
309 118157274
310 119307685
311 120465539
312 121630860
313 122803672
314 123983999
315 125171865
316 126367294
317 127570310
318 128780937
319 129999199
320 131225120
321 132458724
322 133700035
323 134949077
324 136205874
325 137470450
326 138742829
327 140023035
328 141311092
329 142607024
330 143910855
331 145222609
332 146542310
333 147869982
334 149205649
335 150549335
336 151901064
337 153260860
338 154628747
339 156004749
340 157388890
341 158781194
342 160181685
343 161590387
344 163007324
345 164432520
346 165865999
347 167307785
348 168757902
349 170216374
350 171683225
351 173158479
352 174642160
353 176134292
354 177634899
355 179144005
356 180661634
357 182187810
358 183722557
359 185265899
360 186817860
361 188378464
362 189947735
363 191525697
364 193112374
365 194707790
366 196311969
367 197924935
368 199546712
369 201177324
370 202816795
371 204465149
372 206122410
373 207788602
374 209463749
375 211147875
376 212841004
377 214543160
378 216254367
379 217974649
380 219704030
381 221442534
382 223190185
383 224947007
384 226713024
385 228488260
386 230272739
387 232066485
388 233869522
389 235681874
390 237503565
391 239334619
392 241175060
393 243024912
394 244884199
395 246752945
396 248631174
397 250518910
398 252416177
399 254322999
400 256239400
401 258165404
402 260101035
403 262046317
404 264001274
405 265965930
406 267940309
407 269924435
408 271918332
409 273922024
410 275935535
411 277958889
412 279992110
413 282035222
414 284088249
415 286151215
416 288224144
417 290307060
418 292399987
419 294502949
420 296615970
421 298739074
422 300872285
423 303015627
424 305169124
425 307332800
426 309506679
427 311690785
428 313885142
429 316089774
430 318304705
431 320529959
432 322765560
433 325011532
434 327267899
435 329534685
436 331811914
437 334099610
438 336397797
439 338706499
440 341025740
441 343355544
442 345695935
443 348046937
444 350408574
445 352780870
446 355163849
447 357557535
448 359961952
449 362377124
450 364803075
451 367239829
452 369687410
453 372145842
454 374615149
455 377095355
456 379586484
457 382088560
458 384601607
459 387125649
460 389660710
461 392206814
462 394763985
463 397332247
464 399911624
465 402502140
466 405103819
467 407716685
468 410340762
469 412976074
470 415622645
471 418280499
472 420949660
473 423630152
474 426321999
475 429025225
476 431739854
477 434465910
478 437203417
479 439952399
480 442712880
481 445484884
482 448268435
483 451063557
484 453870274
485 456688610
486 459518589
487 462360235
488 465213572
489 468078624
490 470955415
491 473843969
492 476744310
493 479656462
494 482580449
495 485516295
496 488464024
497 491423660
498 494395227
499 497378749
500 500374250
501 503381754
502 506401285
503 509432867
504 512476524
505 515532280
506 518600159
507 521680185
508 524772382
509 527876774
510 530993385
511 534122239
512 537263360
513 540416772
514 543582499
515 546760565
516 549950994
517 553153810
518 556369037
519 559596699
520 562836820
521 566089424
522 569354535
523 572632177
524 575922374
525 579225150
526 582540529
527 585868535
528 589209192
529 592562524
530 595928555
531 599307309
532 602698810
533 606103082
534 609520149
535 612950035
536 616392764
537 619848360
538 623316847
539 626798249
540 630292590
541 633799894
542 637320185
543 640853487
544 644399824
545 647959220
546 651531699
547 655117285
548 658716002
549 662327874
550 665952925
551 669591179
552 673242660
553 676907392
554 680585399
555 684276705
556 687981334
557 691699310
558 695430657
559 699175399
560 702933560
561 706705164
562 710490235
563 714288797
564 718100874
565 721926490
566 725765669
567 729618435
568 733484812
569 737364824
570 741258495
571 745165849
572 749086910
573 753021702
574 756970249
575 760932575
576 764908704
577 768898660
578 772902467
579 776920149
580 780951730
581 784997234
582 789056685
583 793130107
584 797217524
585 801318960
586 805434439
587 809563985
588 813707622
589 817865374
590 822037265
591 826223319
592 830423560
593 834638012
594 838866699
595 843109645
596 847366874
597 851638410
598 855924277
599 860224499
600 864539100
601 868868104
602 873211535
603 877569417
604 881941774
605 886328630
606 890730009
607 895145935
608 899576432
609 904021524
610 908481235
611 912955589
612 917444610
613 921948322
614 926466749
615 930999915
616 935547844
617 940110560
618 944688087
619 949280449
620 953887670
621 958509774
622 963146785
623 967798727
624 972465624
625 977147500
626 981844379
627 986556285
628 991283242
629 996025274
630 1000782405
631 1005554659
632 1010342060
633 1015144632
634 1019962399
635 1024795385
636 1029643614
637 1034507110
638 1039385897
639 1044279999
640 1049189440
641 1054114244
642 1059054435
643 1064010037
644 1068981074
645 1073967570
646 1078969549
647 1083987035
648 1089020052
649 1094068624
650 1099132775
651 1104212529
652 1109307910
653 1114418942
654 1119545649
655 1124688055
656 1129846184
657 1135020060
658 1140209707
659 1145415149
660 1150636410
661 1155873514
662 1161126485
663 1166395347
664 1171680124
665 1176980840
666 1182297519
667 1187630185
668 1192978862
669 1198343574
670 1203724345
671 1209121199
672 1214534160
673 1219963252
674 1225408499
675 1230869925
676 1236347554
677 1241841410
678 1247351517
679 1252877899
680 1258420580
681 1263979584
682 1269554935
683 1275146657
684 1280754774
685 1286379310
686 1292020289
687 1297677735
688 1303351672
689 1309042124
690 1314749115
691 1320472669
692 1326212810
693 1331969562
694 1337742949
695 1343532995
696 1349339724
697 1355163160
698 1361003327
699 1366860249
700 1372733950
701 1378624454
702 1384531785
703 1390455967
704 1396397024
705 1402354980
706 1408329859
707 1414321685
708 1420330482
709 1426356274
710 1432399085
711 1438458939
712 1444535860
713 1450629872
714 1456740999
715 1462869265
716 1469014694
717 1475177310
718 1481357137
719 1487554199
720 1493768520
721 1500000124
722 1506249035
723 1512515277
724 1518798874
725 1525099850
726 1531418229
727 1537754035
728 1544107292
729 1550478024
730 1556866255
731 1563272009
732 1569695310
733 1576136182
734 1582594649
735 1589070735
736 1595564464
737 1602075860
738 1608604947
739 1615151749
740 1621716290
741 1628298594
742 1634898685
743 1641516587
744 1648152324
745 1654805920
746 1661477399
747 1668166785
748 1674874102
749 1681599374
750 1688342625
751 1695103879
752 1701883160
753 1708680492
754 1715495899
755 1722329405
756 1729181034
757 1736050810
758 1742938757
759 1749844899
760 1756769260
761 1763711864
762 1770672735
763 1777651897
764 1784649374
765 1791665190
766 1798699369
767 1805751935
768 1812822912
769 1819912324
770 1827020195
771 1834146549
772 1841291410
773 1848454802
774 1855636749
775 1862837275
776 1870056404
777 1877294160
778 1884550567
779 1891825649
780 1899119430
781 1906431934
782 1913763185
783 1921113207
784 1928482024
785 1935869660
786 1943276139
787 1950701485
788 1958145722
789 1965608874
790 1973090965
791 1980592019
792 1988112060
793 1995651112
794 2003209199
795 2010786345
796 2018382574
797 2025997910
798 2033632377
799 2041285999
800 2048958800
801 2056650804
802 2064362035
803 2072092517
804 2079842274
805 2087611330
806 2095399709
807 2103207435
808 2111034532
809 2118881024
810 2126746935
811 2134632289
812 2142537110
813 2150461422
814 2158405249
815 2166368615
816 2174351544
817 2182354060
818 2190376187
819 2198417949
820 2206479370
821 2214560474
822 2222661285
823 2230781827
824 2238922124
825 2247082200
826 2255262079
827 2263461785
828 2271681342
829 2279920774
830 2288180105
831 2296459359
832 2304758560
833 2313077732
834 2321416899
835 2329776085
836 2338155314
837 2346554610
838 2354973997
839 2363413499
840 2371873140
841 2380352944
842 2388852935
843 2397373137
844 2405913574
845 2414474270
846 2423055249
847 2431656535
848 2440278152
849 2448920124
850 2457582475
851 2466265229
852 2474968410
853 2483692042
854 2492436149
855 2501200755
856 2509985884
857 2518791560
858 2527617807
859 2536464649
860 2545332110
861 2554220214
862 2563128985
863 2572058447
864 2581008624
865 2589979540
866 2598971219
867 2607983685
868 2617016962
869 2626071074
870 2635146045
871 2644241899
872 2653358660
873 2662496352
874 2671654999
875 2680834625
876 2690035254
877 2699256910
878 2708499617
879 2717763399
880 2727048280
881 2736354284
882 2745681435
883 2755029757
884 2764399274
885 2773790010
886 2783201989
887 2792635235
888 2802089772
889 2811565624
890 2821062815
891 2830581369
892 2840121310
893 2849682662
894 2859265449
895 2868869695
896 2878495424
897 2888142660
898 2897811427
899 2907501749
900 2917213650
901 2926947154
902 2936702285
903 2946479067
904 2956277524
905 2966097680
906 2975939559
907 2985803185
908 2995688582
909 3005595774
910 3015524785
911 3025475639
912 3035448360
913 3045442972
914 3055459499
915 3065497965
916 3075558394
917 3085640810
918 3095745237
919 3105871699
920 3116020220
921 3126190824
922 3136383535
923 3146598377
924 3156835374
925 3167094550
926 3177375929
927 3187679535
928 3198005392
929 3208353524
930 3218723955
931 3229116709
932 3239531810
933 3249969282
934 3260429149
935 3270911435
936 3281416164
937 3291943360
938 3302493047
939 3313065249
940 3323659990
941 3334277294
942 3344917185
943 3355579687
944 3366264824
945 3376972620
946 3387703099
947 3398456285
948 3409232202
949 3420030874
950 3430852325
951 3441696579
952 3452563660
953 3463453592
954 3474366399
955 3485302105
956 3496260734
957 3507242310
958 3518246857
959 3529274399
960 3540324960
961 3551398564
962 3562495235
963 3573614997
964 3584757874
965 3595923890
966 3607113069
967 3618325435
968 3629561012
969 3640819824
970 3652101895
971 3663407249
972 3674735910
973 3686087902
974 3697463249
975 3708861975
976 3720284104
977 3731729660
978 3743198667
979 3754691149
980 3766207130
981 3777746634
982 3789309685
983 3800896307
984 3812506524
985 3824140360
986 3835797839
987 3847478985
988 3859183822
989 3870912374
990 3882664665
991 3894440719
992 3906240560
993 3918064212
994 3929911699
995 3941783045
996 3953678274
997 3965597410
998 3977540477
999 3989507499
1000 4001498500