1 0
2 0
3 0
4 2
5 1
6 4
7 2
8 6
9 5
10 8
11 7
12 14
13 10
14 19
15 17
16 26
17 24
18 37
19 32
20 50
21 47
22 65
23 63
24 87
25 83
26 112
27 110
28 143
29 143
30 183
31 182
32 229
33 233
34 285
35 291
36 356
37 363
38 435
39 451
40 531
41 551
42 649
43 671
44 782
45 818
46 937
47 982
48 1126
49 1175
50 1338
51 1406
52 1583
53 1667
54 1873
55 1965
56 2201
57 2318
58 2576
59 2714
60 3010
61 3167
62 3500
63 3688
64 4057
65 4276
66 4695
67 4941
68 5407
69 5700
70 6216
71 6546
72 7132
73 7503
74 8150
75 8584
76 9295
77 9783
78 10587
79 11129
80 12015
81 12641
82 13609
83 14311
84 15396
85 16171
86 17367
87 18250
88 19553
89 20539
90 21986
91 23074
92 24663
93 25888
94 27621
95 28979
96 30890
97 32388
98 34477
99 36149
100 38425
101 40268
102 42770
103 44795
104 47514
105 49766
106 52723
107 55190
108 58431
109 61131
110 64646
111 67632
112 71440
113 74700
114 78863
115 82417
116 86924
117 90831
118 95701
119 99960
120 105261
121 109886
122 115618
123 120680
124 126864
125 132360
126 139065
127 145026
128 152261
129 158751
130 166548
131 173576
132 182004
133 189608
134 198677
135 206931
136 216690
137 225599
138 236125
139 245741
140 257040
141 267451
142 279583
143 290792
144 303853
145 315921
146 329914
147 342945
148 357937
149 371940
150 388044
151 403084
152 420318
153 436510
154 454936
155 472309
156 492058
157 510678
158 531779
159 551776
160 574309
161 595720
162 619811
163 642726
164 668431
165 692977
166 720390
167 746620
168 775880
169 803905
170 835067
171 865029
172 898221
173 930179
174 965552
175 999634
176 1037249
177 1073630
178 1113632
179 1152366
180 1194941
181 1236182
182 1281396
183 1325337
184 1373348
185 1420074
186 1471095
187 1520758
188 1574886
189 1627712
190 1685107
191 1741205
192 1802107
193 1861651
194 1926186
195 1989414
196 2057771
197 2124826
198 2197247
199 2268336
200 2344985
201 2420359
202 2501460
203 2581285
204 2667102
205 2751627
206 2842339
207 2931840
208 3027717
209 3122381
210 3223724
211 3323830
212 3430827
213 3536708
214 3649667
215 3761519
216 3880788
217 3998930
218 4124733
219 4249531
220 4382190
221 4513896
222 4653816
223 4792757
224 4940208
225 5086804
226 5242135
227 5396685
228 5560335
229 5723208
230 5895507
231 6067154
232 6248499
233 6429268
234 6620125
235 6810450
236 7011202
237 7211563
238 7422671
239 7633468
240 7855444
241 8077166
242 8310428
243 8543624
244 8788701
245 9033799
246 9291277
247 9548829
248 9819159
249 10089793
250 10373562
251 10657756
252 10955628
253 11253987
254 11566481
255 11879706
256 12207446
257 12536100
258 12879837
259 13224565
260 13584902
261 13946483
262 14324102
263 14703182
264 15098901
265 15496203
266 15910711
267 16327081
268 16761154
269 17197316
270 17651827
271 18108613
272 18584344
273 19062664
274 19560485
275 20061152
276 20582040
277 21105971
278 21650765
279 22198996
280 22768681
281 23342085
282 23937752
283 24537351
284 25159924
285 25786876
286 26437428
287 27092705
288 27772461
289 28457178
290 29167176
291 29882609
292 30624006
293 31371270
294 32145419
295 32925712
296 33733790
297 34548523
298 35391799
299 36242208
300 37122153
301 38009583
302 38927512
303 39853482
304 40810821
305 41776707
306 42775035
307 43782344
308 44823120
309 45873508
310 46958311
311 48053290
312 49183875
313 50325102
314 51503037
315 52692361
316 53919406
317 55158458
318 56436553
319 57727161
320 59058023
321 60402228
322 61787770
323 63187376
324 64629741
325 66086737
326 67587836
327 69104450
328 70666346
329 72244604
330 73869649
331 75511697
332 77202009
333 78910292
334 80668140
335 82444875
336 84272794
337 86120373
338 88020707
339 89941752
340 91917014
341 93913969
342 95966895
343 98042399
344 100175554
345 102332465
346 104548612
347 106789592
348 109091737
349 111419672
350 113810575
351 116228620
352 118711324
353 121222348
354 123800145
355 126407310
356 129083217
357 131789960
358 134567272
359 137376755
360 140259070
361 143174711
362 146165353
363 149190892
364 152293413
365 155432342
366 158650659
367 161906678
368 165244434
369 168621607
370 172082692
371 175584815
372 179173439
373 182804593
374 186524745
375 190289288
376 194145233
377 198047318
378 202043597
379 206087674
380 210228624
381 214419434
382 218709697
383 223051734
384 227496274
385 231994374
386 236597850
387 241257194
388 246024674
389 250850115
390 255786983
391 260783776
392 265895116
393 271068864
394 276360133
395 281716147
396 287193194
397 292737135
398 298405513
399 304143442
400 310009032
401 315946753
402 322015877
403 328159509
404 334438201
405 340794297
406 347288963
407 353863792
408 360581209
409 367381463
410 374328197
411 381360890
412 388543898
413 395815851
414 403242441
415 410760879
416 418438143
417 426210681
418 434146145
419 442180126
420 450381720
421 458684960
422 467160305
423 475741052
424 484498296
425 493364475
426 502412173
427 511572223
428 520918646
429 530381442
430 540035338
431 549809501
432 559780104
433 569874691
434 580170978
435 590595556
436 601226925
437 611990825
438 622967222
439 634080218
440 645411326
441 656883702
442 668579706
443 680421517
444 692493046
445 704714882
446 717172420
447 729785291
448 742639812
449 755654580
450 768917532
451 782345577
452 796028224
453 809881434
454 823995599
455 838285633
456 852843663
457 867582767
458 882596739
459 897797725
460 913280371
461 928955771
462 944920348
463 961083334
464 977542889
465 994207184
466 1011175334
467 1028354497
468 1045845506
469 1063553613
470 1081581537
471 1099833350
472 1118412794
473 1137222875
474 1156369130
475 1175752634
476 1195480805
477 1215453525
478 1235779338
479 1256356921
480 1277296701
481 1298495452
482 1320065451
483 1341902262
484 1364119352
485 1386611036
486 1409492733
487 1432656743
488 1456220450
489 1480074948
490 1504338756
491 1528901717
492 1553884445
493 1579174590
494 1604894831
495 1630931626
496 1657408791
497 1684211512
498 1711465715
499 1739054400
500 1767105647
501 1795501105
502 1824370075
503 1853593027
504 1883301305
505 1913373126
506 1943942134
507 1974885114
508 2006336993
509 2038173293
510 2070531086
511 2103283620
512 2136570270
513 2170262825
514 2204502053
515 2239158339
516 2274374705
517 2310019270
518 2346237344
519 2382895561
520 2420140689
521 2457837944
522 2496136403
523 2534898861
524 2574276858
525 2614131718
526 2654616350
527 2695590640
528 2737210005
529 2779331725
530 2822113773
531 2865411922
532 2909385597
533 2953889100
534 2999084355
535 3044823048
536 3091269806
537 3138274632
538 3186003676
539 3234305557
540 3283348891
541 3332979611
542 3383369160
543 3434361730
544 3486130349
545 3538517726
546 3591699492
547 3645515630
548 3700144596
549 3755424619
550 3811535873
551 3868314933
552 3925944692
553 3984259011
554 4043443628
555 4103330597
556 4164107409
557 4225604512
558 4288012177
559 4351157935
560 4415235078
561 4480069404
562 4545855856
563 4612418570
564 4679955477
565 4748287658
566 4817616151
567 4887760216
568 4958922672
569 5030921092
570 5103961277
571 5177857708
572 5252819466
573 5328659033
574 5405587357
575 5483415301
576 5562356782
577 5642219491
578 5723220754
579 5805166238
580 5888275176
581 5972351482
582 6057617558
583 6143874113
584 6231346923
585 6319834637
586 6409565147
587 6500335159
588 6592375835
589 6685480650
590 6779884250
591 6875377980
592 6972198599
593 7070135556
594 7169429009
595 7269864948
596 7371687154
597 7474679598
598 7579088089
599 7684694635
600 7791748642
601 7900028545
602 8009787458
603 8120801701
604 8233326566
605 8347136381
606 8462490030
607 8579158228
608 8697403780
609 8816995077
610 8938197178
611 9060776584
612 9185001955
613 9310636068
614 9437951608
615 9566709077
616 9697183451
617 9829133160
618 9962836978
619 10098049662
620 10235053947
621 10373602232
622 10513979790
623 10655936795
624 10799762410
625 10945203058
626 11092552024
627 11241553322
628 11392502763
629 11545142151
630 11699771367
631 11856128225
632 12014516864
633 12174672814
634 12336902659
635 12500939643
636 12667094631
637 12835096791
638 13005261316
639 13177314959
640 13351575566
641 13527767597
642 13706213130
643 13886632481
644 14069352376
645 14254090464
646 14441176185
647 14630324979
648 14821870609
649 15015524241
650 15211624351
651 15409879496
652 15610630978
653 15813584926
654 16019087117
655 16226839529
656 16437192589
657 16649845560
658 16865151949
659 17082808465
660 17303173186
661 17525938561
662 17751467524
663 17979449755
664 18210251249
665 18443559143
666 18679744240
667 18918489139
668 19160169625
669 19404465695
670 19651756127
671 19901718286
672 20154735929
673 20410481884
674 20669344961
675 20930995188
676 21195824594
677 21463500661
678 21734420299
679 22008246344
680 22285381140
681 22565484492
682 22848962013
683 23135470997
684 23425422095
685 23718467846
686 24015024367
687 24314741213
688 24618037951
689 24924561374
690 25234736227
691 25548204715
692 25865396983
693 26185952137
694 26510304028
695 26838088925
696 27169745936
697 27504906583
698 27844015654
699 28186701542
700 28533412682
701 28883774606
702 29238241363
703 29596433404
704 29958810586
705 30324990373
706 30695436290
707 31069762835
708 31448439261
709 31831075034
710 32218145348
711 32609256422
712 33004887329
713 33404641493
714 33809003601
715 34217571897
716 34630837436
717 35048394997
718 35470739579
719 35897463138
720 36329066530
721 36765136423
722 37206180042
723 37651780636
724 38102449636
725 38557767174
726 39018250657
727 39483475147
728 39953964380
729 40429289860
730 40909979746
731 41395602450
732 41886692189
733 42382812065
734 42884502944
735 43391324436
736 43903821703
737 44421551210
738 44945064616
739 45473912739
740 46008654018
741 46548835871
742 47095021136
743 47646753994
744 48204603851
745 48768109294
746 49337846732
747 49913351038
748 50495203200
749 51082935132
750 51677134241
751 52277326675
752 52884107297
753 53496998384
754 54116599427
755 54742429640
756 55375095283
757 56014109713
758 56660086619
759 57312535473
760 57972075002
761 58638211268
762 59311569872
763 59991651232
764 60679088420
765 61373377828
766 62075157710
767 62783921145
768 63500313405
769 64223821596
770 64955098801
771 65693628256
772 66440068065
773 67193898056
774 67955783875
775 68725199036
776 69502817134
777 70288107848
778 71081749998
779 71883209779
780 72693173558
781 73511101282
782 74337687613
783 75172388271
784 76015903290
785 76867685278
786 77728441682
787 78597618667
788 79475932382
789 80362824728
790 81259017275
791 82163948629
792 83078348155
793 84001648042
794 84934586265
795 85876590686
796 86828405232
797 87789454092
798 88760489111
799 89740928227
800 90731532031
801 91731714001
802 92742240759
803 93762522267
804 94793333277
805 95834077100
806 96885537555
807 97947113794
808 99019595452
809 100102378020
810 101196259855
811 102300629508
812 103416294551
813 104542639277
814 105680477440
815 106829189625
816 107989598252
817 109161076981
818 110344457963
819 111539110159
820 112745872020
821 113964109180
822 115194668711
823 116436909124
824 117691687554
825 118958357863
826 120237783599
827 121529315008
828 122833824694
829 124150655902
830 125480691138
831 126823268923
832 128179278806
833 129548055304
834 130930497143
835 132325931949
836 133735268630
837 135157829954
838 136594531850
839 138044693295
840 139509239754
841 140987482813
842 142480358373
843 143987173630
844 145508871277
845 147044754565
846 148595776234
847 150161232029
848 151742085273
849 153337627110
850 154948828090
851 156574975472
852 158217049749
853 159874330629
854 161547809840
855 163236762017
856 164942186245
857 166663353635
858 168401273250
859 170155208478
860 171926179848
861 173713445859
862 175518034548
863 177339200494
864 179177982185
865 181033626745
866 182907183908
867 184797895757
868 186706820278
869 188633195308
870 190578089394
871 192540732873
872 194522206038
873 196521734086
874 198540405431
875 200577441218
876 202633940979
877 204709117788
878 206804083151
879 208918045483
880 211052124296
881 213205523793
882 215379375019
883 217572874121
884 219787164314
885 222021436768
886 224276843205
887 226552570755
888 228849782486
889 231167657414
890 233507371573
891 235868098483
892 238251022830
893 240655314396
894 243082169434
895 245530749415
896 248002263661
897 250495868458
898 253012782053
899 255552156501
900 258115221994
901 260701122783
902 263311101878
903 265944298147
904 268601964225
905 271283234615
906 273989374017
907 276719508913
908 279474917468
909 282254720774
910 285060206431
911 287890491311
912 290746875779
913 293628468109
914 296536582340
915 299470321847
916 302431010077
917 305417746045
918 308431866271
919 311472461357
920 314540881733
921 317636212637
922 320759814499
923 323910768528
924 327090447947
925 330297925424
926 333534589042
927 336799505650
928 340094073441
929 343417355387
930 346770762964
931 350153350425
932 353566544083
933 357009392672
934 360483333141
935 363987409760
936 367523073071
937 371089359222
938 374687733440
939 378317226147
940 381979313792
941 385673022390
942 389399842131
943 393158790568
944 396951373329
945 400776602330
946 404635994182
947 408528556482
948 412455820489
949 416416784693
950 420412996007
951 424443447745
952 428509697969
953 432610735515
954 436748133231
955 440920871246
956 445130538394
957 449376109032
958 453659183675
959 457978732804
960 462336371414
961 466731061038
962 471164433647
963 475635444738
964 480145738077
965 484694265227
966 489282685140
967 493909940350
968 498577706672
969 503284920867
970 508033271251
971 512821690052
972 517651881054
973 522522768072
974 527436071731
975 532390709854
976 537388416050
977 542428103886
978 547511522604
979 552637576856
980 557808033611
981 563021791796
982 568280631004
983 573583445920
984 578932032895
985 584325277089
986 589764992772
987 595250059665
988 600782305177
989 606360604618
990 611986802131
991 617659763951
992 623381352734
993 629150428588
994 634968867717
995 640835526612
996 646752297979
997 652718028956
998 658734631663
999 664800947075
1000 670918901003