lld dp[1<<10]=
{
0,
0,
1,
1,
2,
2,
1,
8,
3,
3,
2,
7,
1,
17,
9,
7,
4,
4,
3,
6,
2,
16,
8,
6,
1,
26,
9,
9,
19,
6,
7,
59,
5,
5,
4,
5,
3,
15,
7,
5,
2,
25,
8,
15,
18,
5,
6,
49,
1,
35,
9,
9,
19,
8,
9,
48,
29,
5,
6,
49,
7,
149,
69,
47,
6,
6,
5,
4,
4,
14,
6,
4,
3,
24,
7,
14,
17,
4,
5,
39,
2,
34,
8,
19,
18,
14,
8,
38,
28,
4,
5,
39,
6,
139,
59,
37,
1,
44,
9,
9,
19,
8,
9,
37,
29,
7,
8,
38,
9,
138,
58,
36,
39,
4,
5,
39,
6,
139,
59,
39,
7,
239,
69,
36,
169,
37,
47,
369,
7,
7,
6,
3,
5,
13,
5,
3,
4,
23,
6,
13,
16,
3,
4,
29,
3,
33,
7,
23,
17,
13,
7,
28,
27,
3,
4,
29,
5,
129,
49,
27,
2,
43,
8,
19,
18,
18,
8,
27,
28,
13,
14,
28,
8,
128,
48,
26,
38,
3,
4,
29,
5,
129,
49,
29,
6,
229,
59,
26,
159,
27,
37,
269,
1,
53,
9,
9,
19,
8,
9,
26,
29,
7,
8,
27,
9,
127,
47,
25,
39,
6,
7,
28,
8,
128,
48,
28,
9,
228,
58,
25,
158,
26,
36,
259,
49,
3,
4,
29,
5,
129,
49,
29,
6,
229,
59,
28,
159,
29,
39,
258,
7,
329,
69,
25,
169,
26,
36,
259,
269,
27,
37,
269,
47,
1269,
469,
247,
8,
8,
7,
2,
6,
12,
4,
2,
5,
22,
5,
12,
15,
2,
3,
19,
4,
32,
6,
22,
16,
12,
6,
18,
26,
2,
3,
19,
4,
119,
39,
17,
3,
42,
7,
29,
17,
22,
7,
17,
27,
12,
13,
18,
7,
118,
38,
16,
37,
2,
3,
19,
4,
119,
39,
19,
5,
219,
49,
16,
149,
17,
27,
169,
2,
52,
8,
19,
18,
18,
8,
16,
28,
17,
18,
17,
8,
117,
37,
15,
38,
12,
13,
18,
14,
118,
38,
18,
8,
218,
48,
15,
148,
16,
26,
159,
48,
2,
3,
19,
4,
119,
39,
19,
5,
219,
49,
18,
149,
19,
29,
158,
6,
319,
59,
15,
159,
16,
26,
159,
259,
17,
27,
169,
37,
1169,
369,
147,
1,
62,
9,
9,
19,
8,
9,
15,
29,
7,
8,
16,
9,
116,
36,
14,
39,
6,
7,
17,
8,
117,
37,
17,
9,
217,
47,
14,
147,
15,
25,
149,
49,
5,
6,
18,
7,
118,
38,
18,
8,
218,
48,
48,
148,
18,
28,
148,
9,
318,
58,
14,
158,
15,
25,
149,
258,
16,
26,
159,
36,
1159,
359,
137,
59,
2,
3,
19,
4,
119,
39,
19,
5,
219,
49,
18,
149,
19,
29,
147,
6,
319,
59,
17,
159,
18,
28,
148,
259,
19,
29,
158,
39,
1158,
358,
136,
7,
419,
69,
14,
169,
15,
25,
149,
269,
16,
26,
159,
36,
1159,
359,
139,
369,
17,
27,
169,
37,
1169,
369,
136,
47,
2169,
469,
137,
1469,
147,
247,
1469,
9,
9,
8,
1,
7,
11,
3,
1,
6,
21,
4,
11,
14,
1,
2,
9,
5,
31,
5,
21,
15,
11,
5,
8,
25,
1,
2,
9,
3,
109,
29,
7,
4,
41,
6,
31,
16,
21,
6,
7,
26,
11,
12,
8,
6,
108,
28,
6,
36,
1,
2,
9,
3,
109,
29,
9,
4,
209,
39,
6,
139,
7,
17,
69,
3,
51,
7,
29,
17,
28,
7,
6,
27,
21,
17,
7,
7,
107,
27,
5,
37,
11,
12,
8,
13,
108,
28,
8,
7,
208,
38,
5,
138,
6,
16,
59,
47,
1,
2,
9,
3,
109,
29,
9,
4,
209,
39,
8,
139,
9,
19,
58,
5,
309,
49,
5,
149,
6,
16,
59,
249,
7,
17,
69,
27,
1069,
269,
47,
2,
61,
8,
19,
18,
18,
8,
5,
28,
17,
18,
6,
8,
106,
26,
4,
38,
16,
17,
7,
18,
107,
27,
7,
8,
207,
37,
4,
137,
5,
15,
49,
48,
11,
12,
8,
13,
108,
28,
8,
14,
208,
38,
104,
138,
8,
18,
48,
8,
308,
48,
4,
148,
5,
15,
49,
248,
6,
16,
59,
26,
1059,
259,
37,
58,
1,
2,
9,
3,
109,
29,
9,
4,
209,
39,
8,
139,
9,
19,
47,
5,
309,
49,
7,
149,
8,
18,
48,
249,
9,
19,
58,
29,
1058,
258,
36,
6,
409,
59,
4,
159,
5,
15,
49,
259,
6,
16,
59,
26,
1059,
259,
39,
359,
7,
17,
69,
27,
1069,
269,
36,
37,
2069,
369,
37,
1369,
47,
147,
469,
1,
71,
9,
9,
19,
8,
9,
4,
29,
7,
8,
5,
9,
105,
25,
3,
39,
6,
7,
6,
8,
106,
26,
6,
9,
206,
36,
3,
136,
4,
14,
39,
49,
5,
6,
7,
7,
107,
27,
7,
8,
207,
37,
48,
137,
7,
17,
38,
9,
307,
47,
3,
147,
4,
14,
39,
247,
5,
15,
49,
25,
1049,
249,
27,
59,
4,
5,
8,
6,
108,
28,
8,
7,
208,
38,
38,
138,
8,
18,
37,
8,
308,
48,
37,
148,
38,
48,
38,
248,
8,
18,
48,
28,
1048,
248,
26,
9,
408,
58,
3,
158,
4,
14,
39,
258,
5,
15,
49,
25,
1049,
249,
29,
358,
6,
16,
59,
26,
1059,
259,
26,
36,
2059,
359,
27,
1359,
37,
137,
369,
69,
1,
2,
9,
3,
109,
29,
9,
4,
209,
39,
8,
139,
9,
19,
36,
5,
309,
49,
7,
149,
8,
18,
37,
249,
9,
19,
47,
29,
1047,
247,
25,
6,
409,
59,
6,
159,
7,
17,
38,
259,
8,
18,
48,
28,
1048,
248,
28,
359,
9,
19,
58,
29,
1058,
258,
25,
39,
2058,
358,
26,
1358,
36,
136,
359,
7,
509,
69,
3,
169,
4,
14,
39,
269,
5,
15,
49,
25,
1049,
249,
29,
369,
6,
16,
59,
26,
1059,
259,
28,
36,
2059,
359,
29,
1359,
39,
139,
358,
469,
7,
17,
69,
27,
1069,
269,
25,
37,
2069,
369,
26,
1369,
36,
136,
359,
47,
3069,
469,
27,
1469,
37,
137,
369,
2469,
47,
147,
469,
247,
10469,
2469,
247
};