0 1
1 1
2 2
3 3
4 5
5 7
6 11
7 15
8 22
9 30
10 12
11 14
12 21
13 24
14 34
15 17
16 21
17 25
18 33
19 39
20 24
21 27
22 34
23 39
24 50
25 30
26 36
27 42
28 50
29 58
30 40
31 44
32 53
33 60
34 71
35 48
36 56
37 63
38 73
39 83
40 60
41 66
42 77
43 85
44 99
45 71
46 80
47 89
48 102
49 113
50 85
51 93
52 106
53 116
54 132
55 98
56 110
57 121
58 135
59 149
60 116
61 125
62 140
63 153
64 171
65 131
66 145
67 158
68 175
69 191
70 151
71 163
72 181
73 195
74 216
75 170
76 186
77 201
78 221
79 239
80 193
81 207
82 227
83 244
84 268
85 214
86 233
87 251
88 273
89 294
90 241
91 257
92 280
93 300
94 326
95 265
96 287
97 307
98 332
99 356
100 295
101 314
102 340
103 362
104 392
105 323
106 347
107 370
108 399
109 425
110 356
111 378
112 407
113 432
114 465
115 387
116 415
117 441
118 472
119 502
120 425
121 449
122 481
123 510
124 546
125 459
126 490
127 519
128 554
129 587
130 500
131 528
132 564
133 595
134 635
135 539
136 573
137 605
138 644
139 680
140 584
141 615
142 654
143 689
144 733
145 626
146 664
147 700
148 742
149 782
150 676
151 710
152 753
153 792
154 839
155 722
156 764
157 803
158 849
159 893
160 776
161 814
162 861
163 903
164 955
165 827
166 872
167 915
168 966
169 1013
170 885
171 927
172 978
173 1024
174 1080
175 940
176 990
177 1037
178 1091
179 1143
180 1004
181 1049
182 1104
183 1155
184 1215
185 1063
186 1117
187 1168
188 1227
189 1283
190 1131
191 1181
192 1241
193 1295
194 1360
195 1196
196 1254
197 1309
198 1373
199 1433
200 1269
201 1323
202 1387
203 1446
204 1516
205 1338
206 1401
207 1461
208 1529
209 1594
210 1417
211 1475
212 1544
213 1608
214 1682
215 1491
216 1559
217 1623
218 1696
219 1766
220 1575
221 1638
222 1712
223 1780
224 1860
225 1655
226 1727
227 1796
228 1875
229 1949
230 1744
231 1812
232 1891
233 1964
234 2049
235 1829
236 1907
237 1981
238 2064
239 2144
240 1925
241 1997
242 2081
243 2160
244 2250
245 2015
246 2098
247 2177
248 2266
249 2351
250 2116
251 2194
252 2284
253 2367
254 2463
255 2213
256 2301
257 2385
258 2480
259 2570
260 2320
261 2403
262 2498
263 2587
264 2689
265 2422
266 2516
267 2606
268 2706
269 2802
270 2536
271 2624
272 2725
273 2820
274 2927
275 2644
276 2744
277 2839
278 2945
279 3047
280 2764
281 2858
282 2965
283 3065
284 3179
285 2879
286 2984
287 3085
288 3198
289 3305
290 3005
291 3105
292 3218
293 3324
294 3444
295 3126
296 3238
297 3345
298 3463
299 3577
300 3260
301 3365
302 3484
303 3597
304 3723
305 3387
306 3505
307 3618
308 3743
309 3863
310 3527
311 3639
312 3765
313 3883
314 4016
315 3662
316 3786
317 3905
318 4037
319 4163
320 3809
321 3927
322 4059
323 4184
324 4324
325 3950
326 4081
327 4207
328 4345
329 4478
330 4105
331 4229
332 4368
333 4500
334 4646
335 4253
336 4391
337 4523
338 4668
339 4808
340 4415
341 4546
342 4692
343 4830
344 4984
345 4571
346 4715
347 4854
348 5007
349 5153
350 4740
351 4878
352 5031
353 5176
354 5337
355 4903
356 5055
357 5201
358 5360
359 5514
360 5081
361 5225
362 5385
363 5538
364 5706
365 5251
366 5410
367 5563
368 5730
369 5891
370 5436
371 5588
372 5756
373 5915
374 6091
375 5615
376 5781
377 5941
378 6116
379 6284
380 5808
381 5967
382 6142
383 6309
384 6493
385 5994
386 6168
387 6336
388 6518
389 6694
390 6196
391 6362
392 6545
393 6720
394 6911
395 6390
396 6572
397 6747
398 6937
399 7121
400 6600
401 6774
402 6965
403 7147
404 7347
405 6803
406 6992
407 7175
408 7374
409 7565
410 7021
411 7203
412 7402
413 7592
414 7800
415 7232
416 7430
417 7621
418 7827
419 8027
420 7460
421 7649
422 7856
423 8055
424 8271
425 7679
426 7885
427 8084
428 8299
429 8507
430 7915
431 8113
432 8329
433 8535
434 8760
435 8144
436 8358
437 8565
438 8789
439 9005
440 8389
441 8595
442 8819
443 9034
444 9268
445 8626
446 8849
447 9065
448 9297
449 9522
450 8881
451 9095
452 9328
453 9552
454 9794
455 9127
456 9359
457 9583
458 9824
459 10058
460 9391
461 9614
462 9856
463 10088
464 10340
465 9647
466 9887
467 10120
468 10371
469 10613
470 9920
471 10152
472 10403
473 10644
474 10905
475 10185
476 10435
477 10677
478 10936
479 11188
480 10469
481 10709
482 10969
483 11220
484 11490
485 10743
486 11002
487 11253
488 11522
489 11783
490 11036
491 11286
492 11556
493 11815
494 12095
495 11321
496 11589
497 11849
498 12128
499 12398
500 11624
501 11883
502 12162
503 12431
504 12721
505 11918
506 12196
507 12466
508 12754
509 13034
510 12232
511 12500
512 12789
513 13068
514 13367
515 12536
516 12824
517 13103
518 13401
519 13691
520 12860
521 13138
522 13437
523 13725
524 14035
525 13175
526 13472
527 13761
528 14070
529 14369
530 13509
531 13797
532 14106
533 14404
534 14724
535 13834
536 14142
537 14441
538 14759
539 15069
540 14180
541 14477
542 14796
543 15105
544 15435
545 14515
546 14833
547 15142
548 15471
549 15791
550 14871
551 15179
552 15509
553 15827
554 16168
555 15218
556 15546
557 15865
558 16205
559 16535
560 15585
561 15903
562 16243
563 16572
564 16924
565 15942
566 16281
567 16611
568 16961
569 17302
570 16321
571 16649
572 17000
573 17340
574 17702
575 16689
576 17039
577 17379
578 17740
579 18092
580 17079
581 17418
582 17780
583 18130
584 18504
585 17459
586 17819
587 18170
588 18543
589 18905
590 17860
591 18210
592 18583
593 18944
594 19329
595 18251
596 18623
597 18985
598 19368
599 19742
600 18665
601 19025
602 19409
603 19782
604 20178
605 19067
606 19450
607 19823
608 20218
609 20603
610 19492
611 19864
612 20260
613 20643
614 21051
615 19907
616 20301
617 20685
618 21092
619 21488
620 20344
621 20727
622 21134
623 21529
624 21949
625 20770
626 21176
627 21572
628 21990
629 22398
630 21220
631 21614
632 22033
633 22440
634 22871
635 21658
636 22076
637 22483
638 22913
639 23333
640 22120
641 22526
642 22957
643 23375
644 23819
645 22571
646 23000
647 23419
648 23862
649 24293
650 23045
651 23463
652 23906
653 24336
654 24792
655 23508
656 23950
657 24381
658 24835
659 25279
660 23996
661 24425
662 24880
663 25323
664 25791
665 24471
666 24925
667 25368
668 25835
669 26291
670 24971
671 25413
672 25881
673 26335
674 26816
675 25460
676 25926
677 26381
678 26861
679 27329
680 25973
681 26427
682 26907
683 27374
684 27868
685 26474
686 26953
687 27421
688 27913
689 28394
690 27001
691 27467
692 27960
693 28440
694 28946
695 27515
696 28007
697 28487
698 28992
699 29486
700 28055
701 28534
702 29040
703 29532
704 30052
705 28583
706 29087
707 29580
708 30099
709 30605
710 29136
711 29628
712 30147
713 30652
714 31185
715 29677
716 30195
717 30701
718 31232
719 31752
720 30245
721 30749
722 31281
723 31800
724 32346
725 30799
726 31330
727 31849
728 32394
729 32927
730 31380
731 31898
732 32444
733 32975
734 33535
735 31949
736 32493
737 33025
738 33584
739 34130
740 32544
741 33075
742 33634
743 34179
744 34753
745 33126
746 33684
747 34230
748 34802
749 35362
750 33736
751 34280
752 34853
753 35412
754 35999
755 34332
756 34904
757 35463
758 36049
759 36623
760 34956
761 35514
762 36101
763 36673
764 37275
765 35567
766 36152
767 36725
768 37326
769 37913
770 36205
771 36777
772 37378
773 37964
774 38580
775 36830
776 37430
777 38017
778 38631
779 39233
780 37484
781 38069
782 38684
783 39285
784 39915
785 38123
786 38737
787 39338
788 39967
789 40583
790 38791
791 39391
792 40021
793 40635
794 41280
795 39446
796 40074
797 40689
798 41333
799 41963
800 40129
801 40743
802 41387
803 42016
804 42676
805 40798
806 41441
807 42071
808 42729
809 43374
810 41497
811 42125
812 42784
813 43428
814 44102
815 42181
816 42839
817 43483
818 44156
819 44816
820 42895
821 43538
822 44212
823 44870
824 45560
825 43595
826 44267
827 44926
828 45615
829 46289
830 44324
831 44982
832 45671
833 46344
834 47049
835 45039
836 45727
837 46401
838 47104
839 47794
840 45785
841 46457
842 47161
843 47850
844 48570
845 46515
846 47218
847 47907
848 48626
849 49331
850 47276
851 47964
852 48684
853 49387
854 50123
855 48023
856 48741
857 49445
858 50180
859 50900
860 48800
861 49503
862 50238
863 50957
864 51709
865 49562
866 50296
867 51016
868 51766
869 52502
870 50356
871 51074
872 51825
873 52560
874 53327
875 51134
876 51884
877 52619
878 53385
879 54137
880 51944
881 52678
882 53445
883 54195
884 54979
885 52739
886 53504
887 54255
888 55038
889 55805
890 53565
891 54315
892 55098
893 55864
894 56664
895 54376
896 55158
897 55925
898 56723
899 57507
900 55220
901 55985
902 56784
903 57567
904 58383
905 56047
906 56845
907 57628
908 58443
909 59243
910 56907
911 57689
912 58505
913 59303
914 60136
915 57752
916 58566
917 59365
918 60197
919 61013
920 58629
921 59427
922 60259
923 61074
924 61924
925 59490
926 60321
927 61137
928 61985
929 62818
930 60385
931 61199
932 62048
933 62880
934 63746
935 61263
936 62111
937 62943
938 63808
939 64658
940 62175
941 63006
942 63872
943 64720
944 65604
945 63071
946 63935
947 64784
948 65667
949 66533
950 64000
951 64848
952 65731
953 66596
954 67497
955 64913
956 65795
957 66661
958 67560
959 68444
960 65861
961 66725
962 67625
963 68508
964 69426
965 66791
966 67690
967 68573
968 69490
969 70391
970 67756
971 68638
972 69556
973 70455
974 71391
975 68705
976 69621
977 70521
978 71456
979 72374
980 69688
981 70587
982 71522
983 72439
984 73393
985 70654
986 71588
987 72506
988 73458
989 74394
990 71656
991 72572
992 73525
993 74460
994 75431
995 72640
996 73592
997 74527
998 75497
999 76451
1000 73660