0 1
1 1
2 2
3 3
4 5
5 7
6 5
7 9
8 10
9 12
10 12
11 14
12 20
13 20
14 21
15 23
16 24
17 24
18 32
19 29
20 35
21 36
22 44
23 47
24 38
25 47
26 49
27 52
28 55
29 58
30 59
31 64
32 66
33 71
34 70
35 78
36 79
37 88
38 87
39 90
40 85
41 87
42 111
43 104
44 102
45 107
46 112
47 113
48 121
49 113
50 130
51 130
52 148
53 153
54 132
55 147
56 149
57 156
58 162
59 149
60 167
61 160
62 178
63 180
64 183
65 198
66 171
67 207
68 205
69 198
70 200
71 210
72 232
73 238
74 217
75 231
76 216
77 239
78 265
79 243
80 250
81 254
82 265
83 272
84 267
85 278
86 267
87 294
88 308
89 280
90 295
91 285
92 331
93 338
94 315
95 337
96 316
97 346
98 358
99 335
100 365
101 330
102 382
103 366
104 360
105 372
106 382
107 418
108 390
109 386
110 399
111 377
112 433
113 450
114 406
115 440
116 426
117 460
118 458
119 445
120 480
121 470
122 496
123 509
124 431
125 461
126 494
127 528
128 526
129 481
130 535
131 504
132 525
133 561
134 526
135 571
136 513
137 603
138 593
139 553
140 564
141 572
142 616
143 588
144 602
145 582
146 582
147 661
148 686
149 638
150 627
151 632
152 679
153 682
154 646
155 675
156 665
157 683
158 744
159 650
160 714
161 699
162 743
163 769
164 684
165 736
166 711
167 774
168 782
169 747
170 789
171 725
172 830
173 809
174 760
175 815
176 806
177 873
178 844
179 810
180 834
181 811
182 910
183 920
184 845
185 859
186 872
187 915
188 923
189 853
190 915
191 899
192 938
193 1006
194 865
195 928
196 913
197 1036
198 1023
199 926
200 999
201 952
202 982
203 1037
204 1029
205 1047
206 940
207 1116
208 1080
209 970
210 1065
211 1028
212 1146
213 1118
214 1087
215 1093
216 1038
217 1161
218 1184
219 1104
220 1115
221 1116
222 1149
223 1145
224 1127
225 1213
226 1177
227 1251
228 1246
229 1146
230 1186
231 1155
232 1314
233 1294
234 1175
235 1270
236 1192
237 1294
238 1337
239 1249
240 1336
241 1200
242 1383
243 1322
244 1238
245 1321
246 1288
247 1440
248 1400
249 1342
250 1374
251 1326
252 1448
253 1509
254 1415
255 1373
256 1370
257 1429
258 1508
259 1406
260 1512
261 1403
262 1496
263 1576
264 1368
265 1467
266 1433
267 1602
268 1595
269 1477
270 1581
271 1488
272 1546
273 1639
274 1510
275 1577
276 1541
277 1702
278 1632
279 1535
280 1626
281 1595
282 1778
283 1658
284 1624
285 1644
286 1584
287 1758
288 1773
289 1650
290 1683
291 1730
292 1798
293 1814
294 1647
295 1823
296 1717
297 1814
298 1908
299 1674
300 1749
301 1714
302 1939
303 1979
304 1723
305 1887
306 1736
307 1896
308 1925
309 1860
310 1930
311 1776
312 2008
313 1945
314 1834
315 1953
316 1924
317 2099
318 2036
319 1930
320 1939
321 1850
322 2075
323 2104
324 1988
325 1973
326 2043
327 2042
328 2130
329 2010
330 2082
331 2087
332 2123
333 2202
334 1996
335 2108
336 2062
337 2313
338 2309
339 2034
340 2190
341 2027
342 2285
343 2303
344 2173
345 2209
346 2107
347 2386
348 2298
349 2120
350 2278
351 2262
352 2402
353 2368
354 2274
355 2252
356 2208
357 2455
358 2454
359 2274
360 2336
361 2331
362 2392
363 2391
364 2367
365 2461
366 2336
367 2472
368 2631
369 2340
370 2415
371 2353
372 2684
373 2672
374 2302
375 2588
376 2349
377 2547
378 2605
379 2492
380 2669
381 2520
382 2765
383 2729
384 2436
385 2631
386 2604
387 2791
388 2658
389 2533
390 2645
391 2503
392 2772
393 2856
394 2703
395 2718
396 2645
397 2792
398 2715
399 2657
400 2786
401 2750
402 2864
403 2980
404 2614
405 2815
406 2732
407 3004
408 3081
409 2667
410 2922
411 2674
412 3019
413 3024
414 2859
415 2927
416 2812
417 3082
418 3001
419 2856
420 2915
421 2944
422 3170
423 3042
424 2988
425 3042
426 2791
427 3240
428 3264
429 3009
430 2994
431 2990
432 3203
433 3206
434 3057
435 3252
436 3095
437 3152
438 3443
439 2988
440 3114
441 3076
442 3405
443 3378
444 3000
445 3367
446 3114
447 3330
448 3406
449 3254
450 3362
451 3082
452 3568
453 3368
454 3106
455 3340
456 3322
457 3581
458 3502
459 3330
460 3396
461 3220
462 3550
463 3690
464 3410
465 3323
466 3372
467 3555
468 3604
469 3383
470 3556
471 3502
472 3628
473 3780
474 3402
475 3467
476 3359
477 3807
478 3842
479 3442
480 3747
481 3429
482 3756
483 3856
484 3594
485 3812
486 3521
487 3954
488 3748
489 3589
490 3814
491 3675
492 4002
493 3823
494 3740
495 3725
496 3615
497 3997
498 4024
499 3755
500 3774
501 3811
502 4032
503 3988
504 3753
505 4004
506 3810
507 4100
508 4115
509 3688
510 3907
511 3864
512 4266
513 4319
514 3742
515 4124
516 3782
517 4018
518 4322
519 3969
520 4227
521 3878
522 4356
523 4338
524 3947
525 4143
526 4138
527 4376
528 4210
529 4187
530 4109
531 3930
532 4318
533 4599
534 4170
535 4266
536 4171
537 4471
538 4425
539 4186
540 4450
541 4242
542 4455
543 4612
544 4122
545 4290
546 4371
547 4647
548 4727
549 4122
550 4531
551 4224
552 4564
553 4589
554 4356
555 4659
556 4316
557 4910
558 4563
559 4366
560 4608
561 4413
562 4954
563 4658
564 4542
565 4559
566 4425
567 4821
568 5047
569 4536
570 4616
571 4622
572 4858
573 4842
574 4485
575 4887
576 4686
577 4997
578 5124
579 4494
580 4581
581 4705
582 5132
583 5070
584 4604
585 5000
586 4528
587 4961
588 5226
589 4936
590 5102
591 4684
592 5317
593 4978
594 4779
595 5014
596 4884
597 5285
598 5203
599 4997
600 5001
601 4862
602 5301
603 5548
604 5100
605 4954
606 5074
607 5178
608 5214
609 5006
610 5339
611 5259
612 5313
613 5464
614 4994
615 5200
616 5080
617 5672
618 5544
619 4924
620 5400
621 5046
622 5552
623 5623
624 5280
625 5522
626 5040
627 5749
628 5611
629 5060
630 5408
631 5248
632 5896
633 5747
634 5419
635 5386
636 5200
637 5830
638 5807
639 5496
640 5491
641 5520
642 5718
643 5860
644 5389
645 5802
646 5472
647 5799
648 6028
649 5300
650 5664
651 5417
652 6021
653 6132
654 5505
655 5998
656 5591
657 5934
658 6084
659 5791
660 5970
661 5634
662 6179
663 5988
664 5482
665 5890
666 5940
667 6380
668 6117
669 5864
670 5826
671 5638
672 6281
673 6358
674 5852
675 5792
676 6080
677 6270
678 6188
679 5863
680 6349
681 6004
682 6182
683 6540
684 5759
685 6119
686 5841
687 6614
688 6651
689 5960
690 6327
691 5961
692 6524
693 6529
694 6269
695 6415
696 5900
697 6614
698 6591
699 5989
700 6440
701 6204
702 6852
703 6574
704 6213
705 6475
706 6074
707 6768
708 6928
709 6443
710 6496
711 6541
712 6488
713 6710
714 6350
715 6662
716 6438
717 6700
718 7113
719 6207
720 6603
721 6405
722 7150
723 7045
724 6512
725 6900
726 6304
727 6973
728 7076
729 6546
730 6933
731 6436
732 7367
733 7035
734 6502
735 6943
736 6744
737 7368
738 7038
739 6714
740 6659
741 6501
742 7327
743 7424
744 6968
745 6873
746 6971
747 7324
748 7102
749 6864
750 7255
751 6926
752 7203
753 7584
754 6756
755 6911
756 6864
757 7636
758 7668
759 6841
760 7526
761 6747
762 7240
763 7539
764 7153
765 7572
766 6886
767 7767
768 7552
769 6888
770 7345
771 7328
772 7792
773 7529
774 7202
775 7315
776 7092
777 7776
778 7912
779 7442
780 7399
781 7248
782 7733
783 7700
784 7235
785 7794
786 7612
787 7881
788 8135
789 7168
790 7594
791 7344
792 8060
793 8330
794 7230
795 7773
796 7290
797 8071
798 8211
799 7790
800 7781
801 7318
802 8396
803 7956
804 7388
805 7823
806 7730
807 8270
808 8037
809 7975
810 8000
811 7498
812 8469
813 8456
814 7632
815 7969
816 7712
817 8134
818 8100
819 7896
820 8355
821 7947
822 8260
823 8776
824 7798
825 7935
826 7877
827 8632
828 8712
829 7722
830 8522
831 7821
832 8576
833 8433
834 8129
835 8538
836 7833
837 9064
838 8449
839 7764
840 8244
841 8444
842 8971
843 8690
844 8195
845 8412
846 7956
847 8763
848 9130
849 8353
850 8426
851 8398
852 8773
853 8775
854 8412
855 8621
856 8514
857 8708
858 9255
859 8104
860 8531
861 8423
862 9350
863 9547
864 8345
865 8939
866 8284
867 9112
868 9144
869 8540
870 9132
871 8318
872 9178
873 8839
874 8508
875 9138
876 8844
877 9547
878 9146
879 8772
880 8839
881 8551
882 9324
883 9475
884 8775
885 9002
886 8893
887 9447
888 9462
889 8884
890 9356
891 8904
892 9382
893 9665
894 8629
895 8910
896 8954
897 10021
898 10015
899 8564
900 9665
901 8849
902 9402
903 9900
904 9135
905 9456
906 8741
907 9957
908 9772
909 8988
910 9415
911 9320
912 10014
913 9646
914 9471
915 9344
916 9028
917 9902
918 10212
919 9554
920 9461
921 9413
922 9830
923 9908
924 9228
925 9839
926 9545
927 9797
928 10347
929 9320
930 9520
931 9416
932 10502
933 10454
934 9364
935 10013
936 9421
937 10093
938 10267
939 9776
940 10199
941 9410
942 10774
943 10148
944 9449
945 10100
946 9747
947 10800
948 10084
949 9978
950 9631
951 9626
952 10604
953 10960
954 9886
955 10175
956 10028
957 10281
958 10476
959 9578
960 10480
961 9934
962 10618
963 10979
964 9796
965 10155
966 10128
967 11048
968 11007
969 9737
970 10431
971 9726
972 10578
973 10984
974 10330
975 10784
976 9733
977 11260
978 10704
979 9929
980 10854
981 10400
982 11150
983 10850
984 10522
985 10587
986 10150
987 10899
988 11410
989 10492
990 10393
991 10777
992 10854
993 10909
994 10415
995 11043
996 10692
997 11255
998 11374
999 10398
1000 10640