1 0
2 0
3 0
4 1
5 1
6 1
7 1
8 2
9 1
10 2
11 1
12 4
13 2
14 4
15 4
16 6
17 5
18 8
19 7
20 11
21 9
22 12
23 11
24 16
25 16
26 19
27 19
28 25
29 24
30 31
31 29
32 38
33 38
34 45
35 49
36 55
37 57
38 66
39 69
40 83
41 82
42 97
43 100
44 114
45 120
46 133
47 143
48 159
49 168
50 188
51 195
52 220
53 231
54 256
55 272
56 299
57 316
58 346
59 367
60 407
61 426
62 467
63 495
64 539
65 572
66 616
67 658
68 713
69 753
70 819
71 861
72 934
73 986
74 1062
75 1126
76 1206
77 1281
78 1369
79 1449
80 1557
81 1641
82 1761
83 1857
84 1991
85 2101
86 2237
87 2365
88 2520
89 2660
90 2835
91 2988
92 3183
93 3352
94 3563
95 3761
96 3988
97 4206
98 4459
99 4695
100 4982
101 5239
102 5552
103 5842
104 6182
105 6510
106 6873
107 7236
108 7643
109 8035
110 8486
111 8914
112 9414
113 9882
114 10416
115 10947
116 11527
117 12105
118 12741
119 13376
120 14082
121 14759
122 15528
123 16282
124 17116
125 17947
126 18847
127 19756
128 20742
129 21723
130 22806
131 23875
132 25055
133 26221
134 27494
135 28777
136 30154
137 31549
138 33049
139 34563
140 36200
141 37831
142 39605
143 41384
144 43309
145 45255
146 47320
147 49435
148 51684
149 53968
150 56409
151 58875
152 61527
153 64195
154 67052
155 69958
156 73033
157 76178
158 79507
159 82907
160 86513
161 90167
162 94066
163 98021
164 102217
165 106498
166 111010
167 115636
168 120505
169 125490
170 130739
171 136101
172 141771
173 147550
174 153637
175 159879
176 166426
177 173139
178 180176
179 187406
180 194993
181 202737
182 210890
183 219236
184 227989
185 236960
186 246346
187 255994
188 266075
189 276418
190 287236
191 298328
192 309945
193 321850
194 334288
195 347059
196 360397
197 374091
198 388365
199 403034
200 418350
201 434047
202 450421
203 467248
204 484784
205 502779
206 521520
207 540795
208 560851
209 581437
210 602888
211 624901
212 647818
213 671352
214 695830
215 721001
216 747116
217 774001
218 801895
219 830580
220 860381
221 890988
222 922780
223 955443
224 989352
225 1024208
226 1060338
227 1097527
228 1136066
229 1175683
230 1216755
231 1258976
232 1302745
233 1347717
234 1394325
235 1442261
236 1491872
237 1542898
238 1595716
239 1650039
240 1706269
241 1764058
242 1823873
243 1885372
244 1948984
245 2014416
246 2082027
247 2151603
248 2223512
249 2297447
250 2373885
251 2452443
252 2533675
253 2617150
254 2703400
255 2792103
256 2883694
257 2977872
258 3075109
259 3175095
260 3278335
261 3384432
262 3493981
263 3606584
264 3722824
265 3842283
266 3965528
267 4092244
268 4222963
269 4357309
270 4495896
271 4638309
272 4785215
273 4936152
274 5091794
275 5251767
276 5416656
277 5586108
278 5760765
279 5940232
280 6125213
281 6315208
282 6511047
283 6712235
284 6919512
285 7132461
286 7351776
287 7577138
288 7809196
289 8047602
290 8293094
291 8545246
292 8804911
293 9071557
294 9346076
295 9628055
296 9918258
297 10216319
298 10523036
299 10838069
300 11162225
301 11495022
302 11837504
303 12189141
304 12550889
305 12922309
306 13304319
307 13696577
308 14099958
309 14514066
310 14939942
311 15377069
312 15826613
313 16287984
314 16762304
315 17249200
316 17749666
317 18263371
318 18791297
319 19333160
320 19890049
321 20461447
322 21048691
323 21651246
324 22270402
325 22905655
326 23558272
327 24227944
328 24915786
329 25621497
330 26346391
331 27089982
332 27853744
333 28637135
334 29441673
335 30266901
336 31114242
337 31983374
338 32875661
339 33790833
340 34730386
341 35693879
342 36682937
343 37697155
344 38738209
345 39805658
346 40901154
347 42024509
348 43177253
349 44359096
350 45571825
351 46815108
352 48090796
353 49398427
354 50740036
355 52115308
356 53526025
357 54972068
358 56455266
359 57975525
360 59534776
361 61132736
362 62771611
363 64451083
364 66173383
365 67938290
366 69747897
367 71602296
368 73503535
369 75451580
370 77448729
371 79494882
372 81592537
373 83741393
374 85944184
375 88200750
376 90513606
377 92882815
378 95310921
379 97798080
380 100346904
381 102957409
382 105632548
383 108372250
384 111179547
385 114054459
386 116999934
387 120016316
388 123106508
389 126270827
390 129512348
391 132831404
392 136231283
393 139712171
394 143277554
395 146927817
396 150666298
397 154493537
398 158413015
399 162425354
400 166534141
401 170739835
402 175046455
403 179454451
404 183967818
405 188587185
406 193316586
407 198156913
408 203112159
409 208183276
410 213374467
411 218686715
412 224124501
413 229688687
414 235383913
415 241211349
416 247175566
417 253277850
418 259522965
419 265912370
420 272450950
421 279139992
422 285984881
423 292987028
424 300151746
425 307480657
426 314979215
427 322649334
428 330496478
429 338522582
430 346733520
431 355131257
432 363721944
433 372507495
434 381494264
435 390684586
436 400084780
437 409697329
438 419528759
439 429581842
440 439863342
441 450375801
442 461126581
443 472118445
444 483358792
445 494850489
446 506601245
447 518614371
448 530897512
449 543454096
450 556292418
451 569415793
452 582832837
453 596547076
454 610567388
455 624897724
456 639546883
457 654519259
458 669823896
459 685465392
460 701453323
461 717792129
462 734491917
463 751557492
464 768999106
465 786821870
466 805036252
467 823648014
468 842667671
469 862101091
470 881959561
471 902249088
472 922981329
473 944162388
474 965804563
475 987914413
476 1010504230
477 1033581071
478 1057157719
479 1081241592
480 1105845924
481 1130978181
482 1156652256
483 1182876150
484 1209664061
485 1237024353
486 1264971508
487 1293514690
488 1322668779
489 1352442998
490 1382853065
491 1413908637
492 1445625959
493 1478014861
494 1511092318
495 1544868891
496 1579361705
497 1614581867
498 1650547243
499 1687269490
500 1724766968
501 1763051627
502 1802142794
503 1842052890
504 1882801866
505 1924402647
506 1966875631
507 2010234835
508 2054501156
509 2099688913
510 2145819976
511 2192909273
512 2240979564
513 2290046060
514 2340132357
515 2391254877
516 2443437341
517 2496696948
518 2551058595
519 2606540086
520 2663167161
521 2720957907
522 2779939621
523 2840130999
524 2901559898
525 2964246136
526 3028218232
527 3093497372
528 3160112564
529 3228085859
530 3297447471
531 3368220168
532 3440435631
533 3514116934
534 3589296972
535 3666000358
536 3744260454
537 3824102960
538 3905562483
539 3988666031
540 4073449170
541 4159939439
542 4248174481
543 4338182787
544 4430002775
545 4523664333
546 4619207273
547 4716662835
548 4816071865
549 4917466723
550 5020890082
551 5126375320
552 5233966648
553 5343698659
554 5455616913
555 5569757828
556 5686168180
557 5804885845
558 5925958987
559 6049427329
560 6175340771
561 6303739760
562 6434676613
563 6568193419
564 6704343890
565 6843171646
566 6984732253
567 7129071693
568 7276246631
569 7426304729
570 7579305275
571 7735297268
572 7894342054
573 8056490355
574 8221805798
575 8390341204
576 8562161860
577 8737323002
578 8915891662
579 9097925539
580 9283494158
581 9472656532
582 9665485071
583 9862041143
584 10062399472
585 10266623401
586 10474790058
587 10686966152
588 10903230536
589 11123652013
590 11348313004
591 11577284615
592 11810651875
593 12048488015
594 12290881643
595 12537908949
596 12789660406
597 13046215629
598 13307668102
599 13574100498
600 13845609338
601 14122279622
602 14404211805
603 14691494087
604 14984230004
605 15282510898
606 15586443339
607 15896122907
608 16211659354
609 16533151057
610 16860712101
611 17194444412
612 17534465816
613 17880881214
614 18233812964
615 18593370151
616 18959678306
617 19332850528
618 19713016892
619 20100294604
620 20494817689
621 20896707212
622 21306102228
623 21723128074
624 22147928159
625 22580632116
626 23021387959
627 23470330606
628 23927612632
629 24393373183
630 24867770173
631 25350947857
632 25843069385
633 26344283442
634 26854758853
635 27374650218
636 27904130756
637 28443360653
638 28992519354
639 29551772644
640 30121305463
641 30701288761
642 31291914655
643 31893359726
644 32505821787
645 33129483924
646 33764550187
647 34411210600
648 35069675289
649 35740140619
650 36422823844
651 37117928065
652 37825678105
653 38546283046
654 39279975060
655 40026971522
656 40787511233
657 41561818702
658 42350140871
659 43152710353
660 43969781812
661 44801594534
662 45648412974
663 46510484521
664 47388080998
665 48281458846
666 49190898543
667 50116665660
668 51059049112
669 52018323078
670 52994786728
671 53988722835
672 55000440661
673 56030231949
674 57078415472
675 58145294059
676 59231196015
677 60336434002
678 61461346698
679 62606258068
680 63771517565
681 64957458458
682 66164442640
683 67392814876
684 68642947843
685 69915197117
686 71209948148
687 72527568897
688 73868455745
689 75232988832
690 76621578406
691 78034616463
692 79472525867
693 80935711765
694 82424610570
695 83939641112
696 85481253045
697 87049879026
698 88645982826
699 90270011569
700 91922444155
701 93603741140
702 95314396815
703 97054887864
704 98825723412
705 100627395057
706 102460428299
707 104325332084
708 106222647074
709 108152897936
710 110116644115
711 112114426935
712 114146822746
713 116214389913
714 118317723972
715 120457401782
716 122634035711
717 124848221994
718 127100592771
719 129391763026
720 131722384915
721 134093092126
722 136504557899
723 138957436900
724 141452422653
725 143990190727
726 146571455516
727 149196915928
728 151867308113
729 154583351416
730 157345806858
731 160155416479
732 163012964676
733 165919215921
734 168874979964
735 171881046941
736 174938249154
737 178047402491
738 181209365833
739 184424980693
740 187695132127
741 191020687360
742 194402560361
743 197841645266
744 201338883762
745 204895198354
746 208511558742
747 212188918339
748 215928276031
749 219730613995
750 223596962520
751 227528334978
752 231525793369
753 235590381378
754 239723194366
755 243925309944
756 248197855109
757 252541941012
758 256958730388
759 261449368865
760 266015054101
761 270656966376
762 275376341749
763 280174396886
764 285052404238
765 290011618883
766 295053351626
767 300178897636
768 305389606659
769 310686813032
770 316071908341
771 321546268416
772 327111327430
773 332768501841
774 338519269627
775 344365092948
776 350307492661
777 356347975249
778 362488108468
779 368729446029
780 375073601921
781 381522175605
782 388076832617
783 394739221211
784 401511055055
785 408394033491
786 415389922239
787 422500472971
788 429727503308
789 437072817908
790 444538290129
791 452125778956
792 459837214437
793 467674510915
794 475639656065
795 483734624167
796 491961461075
797 500322200391
798 508818948872
799 517453803187
800 526228932902
801 535146495063
802 544208726305
803 553417849525
804 562776166185
805 572285965572
806 581949618713
807 591769485064
808 601748003573
809 611887604503
810 622190801355
811 632660095958
812 643298075906
813 654107317987
814 665090486654
815 676250236656
816 687589309670
817 699110440255
818 710816450365
819 722710157294
820 734794466846
821 747072277438
822 759546581640
823 772220365728
824 785096708995
825 798178685159
826 811469465031
827 824972215617
828 838690197955
829 852626672018
830 866784997405
831 881168529976
832 895780726212
833 910625040525
834 925705032859
835 941024259344
836 956586381539
837 972395061629
838 988454068518
839 1004767172100
840 1021338251065
841 1038171184719
842 1055269965373
843 1072638587473
844 1090281158783
845 1108201789904
846 1126404707123
847 1144894144259
848 1163674449249
849 1182749976912
850 1202125203842
851 1221804612693
852 1241792808401
853 1262094402263
854 1282714134921
855 1303656753449
856 1324927131858
857 1346530155792
858 1368470841738
859 1390754217066
860 1413385441585
861 1436369687550
862 1459712265662
863 1483418497672
864 1507493846110
865 1531943786636
866 1556773937457
867 1581989935634
868 1607597559437
869 1633602606312
870 1660011021751
871 1686828771172
872 1714061970077
873 1741716753099
874 1769799412160
875 1798316261240
876 1827273767737
877 1856678426880
878 1886536893416
879 1916855848543
880 1947642135069
881 1978902624271
882 2010644357257
883 2042874401118
884 2075599994776
885 2108828408814
886 2142567087266
887 2176823510210
888 2211605330903
889 2246920242040
890 2282776114461
891 2319180860762
892 2356142575546
893 2393669392885
894 2431769637020
895 2470451676981
896 2509724069177
897 2549595418204
898 2590074524164
899 2631170237169
900 2672891603372
901 2715247720268
902 2758247893198
903 2801901477658
904 2846218036311
905 2891207189947
906 2936878771720
907 2983242673716
908 3030309003609
909 3078087931022
910 3126589849156
911 3175825213693
912 3225804708411
913 3276539081944
914 3328039315782
915 3380316464177
916 3433381813577
917 3487246726265
918 3541922804270
919 3597421730687
920 3653755430220
921 3710935908540
922 3768975426274
923 3827886326186
924 3887681206594
925 3948372753885
926 4009973918566
927 4072497742917
928 4135957532858
929 4200366693067
930 4265738903113
931 4332087938007
932 4399427855245
933 4467772812921
934 4537137257544
935 4607535742275
936 4678983109988
937 4751494318029
938 4825084618150
939 4899769383804
940 4975564288468
941 5052485125611
942 5130548003358
943 5209769153843
944 5290165126240
945 5371752598836
946 5454548576232
947 5538570201714
948 5623834941539
949 5710360408744
950 5798164554765
951 5887265475384
952 5977681612029
953 6069431556403
954 6162534258019
955 6257008819990
956 6352874704722
957 6450151541299
958 6548859324912
959 6649018222030
960 6750648773292
961 6853771693984
962 6958408086366
963 7064579233995
964 7172306812038
965 7281612683658
966 7392519112486
967 7505048562460
968 7619223900563
969 7735068197294
970 7852604945529
971 7971857844375
972 8092851020867
973 8215608815679
974 8340156013550
975 8466517617555
976 8594719077639
977 8724786075694
978 8856744752936
979 8990621486297
980 9126443120514
981 9264236745474
982 9404029932887
983 9545850504996
984 9689726775002
985 9835687315540
986 9983761200854
987 10133977778962
988 10286366904186
989 10440958711749
990 10597783859559
991 10756873296838
992 10918258502959
993 11081971254914
994 11248043879460
995 11416509010993
996 11587399835508
997 11760749862460
998 11936593170629
999 12114964167219
1000 12295897839091