1 1
2 8
3 35
4 72
5 133
6 189
7 216
8 224
9 280
10 376
11 411
12 496
13 533
14 472
15 568
16 624
17 712
18 720
19 784
20 783
21 908
22 946
23 992
24 945
25 1062
26 1072
27 1081
28 1107
29 1153
30 1161
31 1224
32 1288
33 1376
34 1377
35 1449
36 1459
37 1547
38 1496
39 1504
40 1593
41 1592
42 1712
43 1719
44 1648
45 1783
46 1800
47 1837
48 1864
49 1809
50 1935
51 1891
52 2016
53 2052
54 2152
55 2143
56 2080
57 2233
58 2106
59 2269
60 2268
61 2232
62 2323
63 2224
64 2322
65 2483
66 2403
67 2376
68 2440
69 2467
70 2538
71 2710
72 2584
73 2565
74 2619
75 2593
76 2782
77 2825
78 2836
79 2800
80 2827
81 2962
82 2925
83 2889
84 2808
85 2952
86 3006
87 3016
88 3168
89 3104
90 3132
91 3097
92 3320
93 3160
94 3195
95 3105
96 3258
97 3339
98 3321
99 3349
100 3312
101 3439
102 3403
103 3466
104 3440
105 3555
106 3600
107 3528
108 3529
109 3609
110 3709
111 3618
112 3619
113 3592
114 3655
115 3861
116 3824
117 3953
118 3825
119 3925
120 3781
121 3736
122 3915
123 3996
124 4041
125 3952
126 4105
127 4077
128 4096
129 4222
130 4185
131 4221
132 4256
133 4104
134 4266
135 4248
136 4131
137 4537
138 4347
139 4392
140 4168
141 4312
142 4527
143 4320
144 4465
145 4483
146 4536
147 4563
148 4681
149 4932
150 4608
151 4600
152 4464
153 4672
154 4951
155 4744
156 4887
157 4680
158 4528
159 4914
160 4825
161 4968
162 4942
163 4824
164 4896
165 4915
166 5113
167 5194
168 5185
169 4978
170 5067
171 5112
172 5041
173 5167
174 5157
175 5040
176 5131
177 5283
178 5257
179 5382
180 5463
181 5211
182 5193
183 5400
184 5464
185 5328
186 5337
187 5472
188 5482
189 5427
190 5552
191 5256
192 5662
193 5473
194 5544
195 5706
196 5751
197 5616
198 5724
199 5850
200 5860
201 5688
202 5643
203 5841
204 5680
205 5851
206 6030
207 5859
208 5769
209 5896
210 6155
211 5832
212 5994
213 5940
214 5984
215 6049
216 6048
217 5977
218 5967
219 6436
220 6075
221 6147
222 6112
223 6318
224 6175
225 6371
226 6301
227 6156
228 6256
229 6192
230 6273
231 6345
232 6210
233 6201
234 6336
235 6328
236 6264
237 6543
238 6507
239 6534
240 6408
241 6480
242 6624
243 6453
244 6625
245 6849
246 6814
247 6877
248 6669
249 6920
250 6904
251 6688
252 6696
253 6859
254 6912
255 6929
256 7254
257 6894
258 6939
259 6903
260 6777
261 7029
262 7219
263 6993
264 6931
265 6994
266 7011
267 7136
268 7048
269 6840
270 7660
271 7174
272 7129
273 7451
274 7453
275 7291
276 7389
277 7192
278 7515
279 6985
280 7227
281 7155
282 7201
283 7264
284 7272
285 7317
286 7568
287 7398
288 7669
289 7542
290 7498
291 7200
292 7344
293 7874
294 7804
295 7632
296 7892
297 7883
298 7704
299 7740
300 7533
301 7687
302 7416
303 7750
304 7876
305 7840
306 7668
307 7722
308 7803
309 7939
310 7714
311 8091
312 7587
313 7965
314 7659
315 7713
316 8218
317 7776
318 7930
319 8290
320 7857
321 7929
322 8182
323 8308
324 7920
325 8325
326 8046
327 8056
328 8353
329 8487
330 8136
331 8379
332 8100
333 8263
334 8577
335 8208
336 8200
337 8343
338 8226
339 8326
340 8137
341 8731
342 8397
343 8505
344 8416
345 8415
346 8569
347 8496
348 8371
349 8289
350 8622
351 8586
352 8497
353 8523
354 8595
355 9019
356 8587
357 8641
358 8965
359 8821
360 8648
361 8623
362 8632
363 8658
364 8649
365 8560
366 8352
367 9189
368 8730
369 8713
370 8910
371 8739
372 8667
373 8712
374 9001
375 9190
376 9181
377 9207
378 9271
379 9054
380 9144
381 9127
382 8919
383 9080
384 8856
385 9072
386 8865
387 9216
388 9243
389 9396
390 9073
391 9325
392 9171
393 9802
394 9262
395 9424
396 9370
397 9352
398 9477
399 9306
400 9225
401 9351
402 9136
403 9315
404 9504
405 9099
406 9522
407 9441
408 9639
409 9432
410 9288
411 10197
412 9523
413 9369
414 9577
415 9775
416 9423
417 9631
418 9603
419 9901
420 9360
421 9549
422 9649
423 9675
424 10054
425 9666
426 9757
427 10198
428 9883
429 9909
430 10025
431 9568
432 9640
433 9729
434 9927
435 9999
436 9784
437 10035
438 10027
439 9855
440 10044
441 10062
442 10018
443 10521
444 10207
445 10324
446 10088
447 10072
448 9801
449 9990
450 10053
451 10081
452 10297
453 9936
454 10270
455 10790
456 10170
457 10395
458 9864
459 10467
460 10431
461 10125
462 10981
463 10144
464 10179
465 10314
466 10459
467 10693
468 10377
469 10333
470 10387
471 10441
472 10602
473 10585
474 10359
475 10557
476 10548
477 10810
478 10657
479 10305
480 10692
481 10296
482 10593
483 11305
484 10656
485 10422
486 10512
487 10936
488 10368
489 10881
490 10953
491 10755
492 10720
493 10909
494 10683
495 10926
496 10774
497 10854
498 11035
499 11107
500 10962
501 11052
502 11024
503 11033
504 11025
505 11206
506 10746
507 11178
508 11233
509 11070
510 11043
511 11016
512 11196
513 10998
514 11384
515 11521
516 11611
517 10809
518 11017
519 10935
520 11124
521 11080
522 11232
523 11403
524 11367
525 11224
526 10872
527 11250
528 12185
529 12302
530 11296
531 11169
532 11764
533 11115
534 11322
535 11259
536 11475
537 11241
538 11881
539 11304
540 11843
541 11926
542 11637
543 11313
544 12070
545 12440
546 11467
547 11853
548 11664
549 11772
550 11530
551 11809
552 11628
553 11682
554 11556
555 11584
556 12241
557 11593
558 12150
559 11619
560 11800
561 11691
562 12304
563 11376
564 11656
565 11773
566 11817
567 12322
568 12177
569 12187
570 12043
571 12230
572 11880
573 12024
574 12051
575 11826
576 12006
577 12025
578 12078
579 12331
580 12034
581 12313
582 11808
583 12429
584 12015
585 12169
586 12655
587 12016
588 11745
589 12411
590 12376
591 12421
592 12069
593 12168
594 12088
595 12402
596 12240
597 12249
598 12160
599 12104
600 12466
601 13292
602 13139
603 12547
604 12403
605 12232
606 13069
607 12583
608 12475
609 12375
610 12681
611 12781
612 12456
613 12258
614 12610
615 12680
616 12384
617 12573
618 12582
619 12195
620 12636
621 12870
622 12501
623 12718
624 12321
625 12592
626 13283
627 12528
628 12529
629 12736
630 12447
631 13373
632 13113
633 13050
634 13510
635 12790
636 12915
637 12834
638 12897
639 12753
640 13049
641 13158
642 13123
643 12879
644 13481
645 12312
646 12942
647 13024
648 12664
649 12699
650 12951
651 12744
652 13041
653 13077
654 13213
655 13679
656 13068
657 13285
658 12888
659 13419
660 13194
661 13717
662 12979
663 13456
664 13105
665 12762
666 13231
667 12960
668 13014
669 13149
670 12816
671 13104
672 14075
673 15496
674 13771
675 13168
676 13536
677 12825
678 13266
679 13338
680 13474
681 13464
682 13329
683 14292
684 13609
685 13455
686 13735
687 13131
688 13528
689 13203
690 13401
691 13473
692 13446
693 13546
694 13726
695 13257
696 13942
697 14374
698 13663
699 13815
700 14888
701 13842
702 13600
703 13635
704 14058
705 13581
706 13816
707 13969
708 13672
709 13518
710 13744
711 13960
712 13870
713 13789
714 14112
715 13392
716 14723
717 14041
718 15509
719 13770
720 13698
721 14311
722 13707
723 13905
724 13824
725 13833
726 13896
727 14507
728 14570
729 14489
730 14113
731 13761
732 14050
733 14346
734 14157
735 16868
736 13752
737 14283
738 13959
739 14435
740 14301
741 14230
742 14355
743 14634
744 14094
745 14085
746 14561
747 14022
748 14624
749 14626
750 14480
751 14734
752 14580
753 14302
754 14239
755 14535
756 14545
757 14148
758 14896
759 14607
760 14463
761 14365
762 14445
763 14536
764 13968
765 15012
766 14409
767 14589
768 14877
769 14750
770 14751
771 14760
772 14643
773 14202
774 14419
775 14337
776 14652
777 14176
778 14850
779 15211
780 14211
781 15833
782 14661
783 14787
784 14400
785 14598
786 16211
787 14724
788 14994
789 14931
790 14806
791 14688
792 15102
793 14517
794 15400
795 14752
796 15300
797 14769
798 15246
799 14544
800 15255
801 14869
802 14986
803 14328
804 15363
805 14932
806 16040
807 14832
808 15435
809 14472
810 15508
811 15706
812 14985
813 14715
814 15517
815 14841
816 14995
817 15192
818 14967
819 15803
820 15327
821 15120
822 15200
823 15228
824 15328
825 15571
826 15112
827 15219
828 15282
829 15868
830 16343
831 15121
832 15175
833 15174
834 15499
835 15525
836 15291
837 15732
838 14958
839 15624
840 15462
841 15336
842 15147
843 15264
844 15354
845 17498
846 15472
847 15588
848 15885
849 15543
850 15256
851 15201
852 16354
853 15606
854 15687
855 15993
856 16074
857 15859
858 15786
859 16165
860 15417
861 15562
862 16048
863 15966
864 15795
865 15534
866 15940
867 15904
868 16047
869 15625
870 15480
871 14904
872 16525
873 16075
874 16092
875 16183
876 15597
877 15471
878 15858
879 16452
880 15930
881 15957
882 16496
883 16056
884 15931
885 15688
886 16379
887 15768
888 16317
889 16426
890 16066
891 16245
892 15921
893 15840
894 15723
895 15408
896 15777
897 16201
898 16623
899 16505
900 16173
901 16524
902 16451
903 16444
904 16552
905 16398
906 16246
907 15903
908 16408
909 16038
910 16120
911 16371
912 15849
913 16758
914 16110
915 16596
916 16272
917 16506
918 16281
919 16766
920 16381
921 16164
922 16975
923 16488
924 16578
925 16570
926 16498
927 16542
928 15984
929 16200
930 16892
931 16705
932 16470
933 16840
934 16821
935 16407
936 16579
937 16704
938 16497
939 16939
940 16479
941 16614
942 16353
943 17531
944 16192
945 16740
946 16624
947 18817
948 17216
949 16227
950 16642
951 17010
952 16344
953 16722
954 16822
955 16587
956 16885
957 17153
958 17271
959 17316
960 17209
961 17191
962 16633
963 17623
964 16803
965 17074
966 16992
967 16659
968 17639
969 16605
970 17046
971 17011
972 17065
973 16713
974 17263
975 17343
976 17037
977 17461
978 19037
979 16416
980 17136
981 16768
982 17416
983 16983
984 17055
985 17585
986 17137
987 17522
988 16929
989 17118
990 17702
991 18299
992 17371
993 17506
994 17181
995 18037
996 16794
997 17622
998 17272
999 17397
1000 17857