0 1
1 9
2 9
3 27
4 36
5 46
6 64
7 68
8 63
9 81
10 117
11 108
12 108
13 146
14 154
15 199
16 187
17 216
18 181
19 207
20 207
21 225
22 256
23 271
24 288
25 337
26 324
27 307
28 328
29 341
30 396
31 443
32 388
33 423
34 463
35 477
36 424
37 495
38 469
39 523
40 502
41 432
42 531
43 572
44 603
45 523
46 592
47 666
48 667
49 695
50 685
51 685
52 739
53 746
54 739
55 683
56 684
57 802
58 754
59 845
60 793
61 833
62 865
63 846
64 871
65 928
66 927
67 934
68 837
69 1016
70 909
71 991
72 1062
73 1015
74 1018
75 1053
76 1093
77 1088
78 1134
79 1133
80 1144
81 1196
82 1231
83 1207
84 1188
85 1277
86 1225
87 1288
88 1206
89 1358
90 1422
91 1278
92 1359
93 1396
94 1444
95 1385
96 1387
97 1442
98 1359
99 1441
100 1489
101 1468
102 1611
103 1523
104 1476
105 1
106 1573
107 1691
108 1648
109 1642
110 1459
111 1682
112 1519
113 1738
114 1521
115 1823
116 1693
117 1773
118 1764
119 1673
120 1702
121 1829
122 1782
123 1952
124 1792
125 1836
126 1827
127 1934
128 1170
129 2115
130 1999
131 1925
132 1828
133 1907
134 1998
135 1981
136 2053
137 2089
138 2071
139 2187
140 2214
141 2132
142 2176
143 2141
144 2143
145 2303
146 2304
147 2258
148 2326
149 2258
150 2305
151 2392
152 2332
153 1540
154 2502
155 2421
156 2395
157 2449
158 2376
159 2377
160 2574
161 2557
162 2511
163 2543
164 1
165 2537
166 2644
167 2637
168 2646
169 2741
170 2656
171 1630
172 2791
173 2673
174 2782
175 2785
176 2836
177 2871
178 2821
179 2834
180 2835
181 2912
182 2728
183 3006
184 2952
185 3007
186 1
187 3077
188 3097
189 3222
190 3109
191 3079
192 2899
193 3077
194 1
195 3006
196 3078
197 3106
198 3078
199 3259
200 2989
201 3276
202 3285
203 3329
204 2340
205 3472
206 1
207 3439
208 3393
209 3338
210 3466
211 3464
212 3537
213 3555
214 3385
215 3475
216 1
217 3511
218 3672
219 3565
220 3475
221 3455
222 3609
223 3654
224 3663
225 3708
226 3577
227 3727
228 3736
229 3726
230 3852
231 1
232 3895
233 3997
234 3987
235 4019
236 3807
237 3772
238 3978
239 4042
240 3907
241 4027
242 3871
243 3718
244 4003
245 4194
246 4104
247 4113
248 4239
249 4114
250 4147
251 4231
252 4014
253 4285
254 1
255 4301
256 4356
257 4211
258 4321
259 4509
260 4213
261 4383
262 4383
263 4374
264 4437
265 4517
266 4536
267 4544
268 4597
269 4481
270 4456
271 4599
272 4537
273 4499
274 4581
275 4491
276 4491
277 4645
278 4726
279 4546
280 4747
281 4535
282 1
283 4889
284 4761
285 1
286 4738
287 4995
288 4735
289 5027
290 4905
291 4978
292 4936
293 5032
294 5049
295 5002
296 4905
297 4994
298 5098
299 4949
300 5176
301 5116
302 1
303 5157
304 5085
305 5266
306 5059
307 5239
308 5157
309 5211
310 5247
311 5275
312 5274
313 5446
314 1
315 5354
316 5386
317 5482
318 5329
319 5409
320 5373
321 5246
322 5455
323 5444
324 1
325 5762
326 5437
327 5427
328 5671
329 5599
330 5635
331 5881
332 5724
333 5624
334 5719
335 5696
336 5896
337 5894
338 5554
339 5751
340 5967
341 5733
342 5922
343 5966
344 5859
345 5905
346 5941
347 6085
348 5959
349 6003
350 5842
351 6039
352 6012
353 6049
354 5914
355 6178
356 6057
357 6274
358 6298
359 6282
360 6201
361 6367
362 6354
363 6209
364 6358
365 6282
366 6427
367 6469
368 6381
369 6416
370 6403
371 6335
372 6175
373 6523
374 1
375 6463
376 6418
377 6777
378 6534
379 6748
380 6571
381 6695
382 6691
383 6614
384 6732
385 6794
386 1
387 6731
388 6997
389 6731
390 6535
391 6919
392 6733
393 6893
394 6955
395 6902
396 6912
397 7064
398 7065
399 6921
400 6948
401 7021
402 1
403 7252
404 7039
405 6967
406 7297
407 7273
408 7147
409 7147
410 7146
411 7254
412 7147
413 7327
414 7173
415 7195
416 1
417 7361
418 7477
419 7334
420 5230
421 7463
422 5230
423 7218
424 7342
425 7506
426 7174
427 7532
428 7579
429 7757
430 7582
431 7758
432 7507
433 7879
434 5320
435 7766
436 7825
437 7767
438 7803
439 7802
440 7759
441 7865
442 7897
443 7876
444 7938
445 7906
446 7804
447 7874
448 7884
449 7991
450 7857
451 8255
452 8163
453 8029
454 8208
455 8082
456 1
457 8181
458 7975
459 8054
460 8317
461 8127
462 8181
463 8334
464 8091
465 8344
466 8433
467 8262
468 1
469 8536
470 8163
471 8397
472 8503
473 8542
474 8388
475 8626
476 8163
477 8721
478 8509
479 8649
480 8406
481 8657
482 8541
483 8767
484 8659
485 8594
486 6210
487 8986
488 8577
489 8594
490 8683
491 1
492 8866
493 9005
494 8947
495 8838
496 8883
497 9036
498 8875
499 8923
500 8569
501 9206
502 8935
503 9152
504 1
505 9052
506 9163
507 8765
508 9076
509 9261
510 9136
511 9439
512 9207
513 9305
514 9283
515 9262
516 9135
517 9559
518 9414
519 9377
520 9376
521 1
522 9514
523 9658
524 9469
525 9584
526 9493
527 9739
528 9622
529 9751
530 3700
531 9711
532 9667
533 9855
534 7020
535 9745
536 9505
537 9729
538 9702
539 9602
540 9712
541 9828
542 9693
543 9729
544 10078
545 6920
546 9936
547 9973
548 9919
549 10071
550 9784
551 10171
552 1
553 10327
554 9972
555 10223
556 10045
557 10216
558 10215
559 10258
560 10225
561 10323
562 10264
563 10035
564 10377
565 10348
566 9982
567 10549
568 10345
569 10207
570 10405
571 10385
572 10692
573 10556
574 10657
575 10592
576 10396
577 10832
578 10603
579 10457
580 10684
581 10477
582 10602
583 10656
584 10675
585 10925
586 10456
587 10989
588 1
589 10836
590 10558
591 10826
592 10798
593 10988
594 10656
595 10993
596 10989
597 10909
598 10963
599 11106
600 11205
601 11467
602 11179
603 11079
604 11296
605 10891
606 1
607 11209
608 11161
609 11394
610 1
611 11088
612 11152
613 11313
614 11457
615 1
616 11458
617 11547
618 11502
619 11686
620 11098
621 11546
622 11539
623 11636
624 11421
625 11501
626 11485
627 11663
628 11611
629 1
630 11763
631 11792
632 11601
633 11897
634 11995
635 11637
636 11871
637 11945
638 11629
639 11827
640 11898
641 11746
642 11745
643 11902
644 12204
645 12087
646 11944
647 11888
648 12178
649 12095
650 11799
651 1
652 12214
653 12204
654 12061
655 12184
656 1
657 1
658 12415
659 12142
660 12232
661 12485
662 12339
663 12429
664 12379
665 12258
666 12294
667 12421
668 12268
669 12752
670 12564
671 12466
672 12375
673 12596
674 12465
675 12329
676 12535
677 12655
678 12358
679 12854
680 12862
681 12545
682 12744
683 12655
684 12871
685 12645
686 12574
687 13069
688 12886
689 12979
690 12708
691 12995
692 12988
693 13005
694 13033
695 12914
696 1
697 13211
698 13257
699 13166
700 12958
701 13212
702 13249
703 13212
704 13069
705 12905
706 13356
707 13312
708 13311
709 13262
710 13294
711 13481
712 13354
713 12996
714 13393
715 13292
716 13545
717 13257
718 13444
719 13509
720 13294
721 13492
722 13564
723 13526
724 13576
725 13518
726 13501
727 13869
728 13708
729 13526
730 13627
731 13608
732 13501
733 13762
734 13761
735 13905
736 13804
737 13625
738 13816
739 13964
740 13789
741 13834
742 13864
743 13932
744 14068
745 14039
746 10360
747 14373
748 14173
749 14095
750 13923
751 14474
752 14076
753 14004
754 14067
755 13915
756 14338
757 14369
758 14148
759 1
760 14319
761 14212
762 14329
763 14823
764 13978
765 14446
766 14598
767 14653
768 14662
769 14725
770 14427
771 14822
772 14686
773 14563
774 14472
775 14728
776 14742
777 14491
778 14857
779 14633
780 14679
781 14715
782 14761
783 14932
784 15277
785 14615
786 14841
787 15002
788 14895
789 14869
790 15082
791 14931
792 14913
793 15178
794 1
795 14994
796 15178
797 15211
798 14815
799 15344
800 15418
801 15407
802 15136
803 15147
804 15301
805 15422
806 15174
807 15227
808 15325
809 15417
810 15319
811 15358
812 15381
813 15435
814 15505
815 15425
816 15418
817 15695
818 15364
819 15652
820 15463
821 15758
822 15192
823 15922
824 15696
825 15787
826 15475
827 15715
828 15697
829 15874
830 1
831 15875
832 15919
833 15823
834 16129
835 16271
836 15958
837 15714
838 15957
839 15947
840 16056
841 16084
842 1
843 16001
844 15973
845 16064
846 16039
847 16166
848 15859
849 16309
850 16225
851 16633
852 16183
853 16316
854 1
855 16308
856 16444
857 16577
858 16534
859 16515
860 16669
861 16793
862 16569
863 16525
864 16479
865 16474
866 16533
867 16687
868 16561
869 16389
870 1
871 16713
872 16632
873 16883
874 16675
875 16498
876 16597
877 17087
878 16695
879 16858
880 16864
881 17118
882 17245
883 17068
884 16732
885 17046
886 17164
887 17065
888 16921
889 17152
890 16911
891 17497
892 17386
893 17182
894 17407
895 17215
896 17587
897 17324
898 17362
899 17477
900 17506
901 17424
902 17136
903 1
904 17431
905 17407
906 1
907 17905
908 17299
909 17515
910 17352
911 17361
912 17532
913 17569
914 17775
915 17416
916 17766
917 17667
918 17641
919 17842
920 17838
921 17874
922 18055
923 17658
924 18171
925 17899
926 17659
927 17659
928 17791
929 17937
930 17874
931 18073
932 17884
933 18234
934 18004
935 18252
936 18226
937 18243
938 17947
939 18377
940 18037
941 17974
942 17964
943 18016
944 18055
945 18226
946 18289
947 18431
948 18243
949 18379
950 18424
951 18477
952 18361
953 18396
954 1
955 18631
956 1
957 18764
958 18265
959 18512
960 18585
961 18865
962 18738
963 18631
964 18484
965 18604
966 18613
967 18716
968 18928
969 19027
970 18724
971 18863
972 19018
973 18994
974 19027
975 19026
976 19057
977 19117
978 19225
979 19249
980 19278
981 1
982 19114
983 19097
984 19296
985 19213
986 19125
987 18955
988 19152
989 19242
990 18883
991 19481
992 19197
993 19386
994 19576
995 19188
996 19332
997 19624
998 1
999 19448
1000 19702