1000 1
998
47 2
56 1
40 1
29 1
67 1
4 2
78 1
4 1
23 2
33 2
24 1
19 1
95 1
96 1
78 1
63 1
73 2
82 2
27 2
11 1
50 1
31 2
67 1
82 2
13 1
23 1
73 2
67 1
74 1
12 1
6 1
56 1
80 1
5 1
8 2
56 1
72 2
93 1
44 1
41 1
84 2
14 1
76 2
2 1
60 1
51 2
37 1
78 1
85 1
83 2
98 1
35 2
81 1
71 2
28 1
96 2
4 2
7 2
89 2
99 1
38 1
21 2
53 2
96 2
6 2
25 2
27 1
32 2
57 1
4 1
93 1
99 2
41 2
94 1
48 1
79 1
18 2
27 1
49 2
19 1
93 2
69 2
74 1
69 2
12 2
57 2
58 1
79 2
27 2
22 1
41 2
98 2
14 2
93 1
69 2
26 2
96 1
43 2
99 2
39 1
94 1
49 2
91 2
4 2
94 2
31 2
68 2
23 1
69 2
34 1
5 2
74 1
97 1
31 2
11 1
81 2
43 1
93 1
76 1
17 2
42 1
50 2
81 1
94 2
58 1
91 2
33 1
91 2
75 2
40 1
36 1
5 1
72 2
57 2
13 1
67 1
32 2
35 2
12 1
93 1
95 1
27 2
45 2
48 2
78 1
70 2
47 2
27 1
19 1
32 1
86 2
77 1
94 1
93 2
78 1
5 1
83 1
31 1
13 1
89 1
18 1
78 2
100 2
72 2
93 2
34 2
91 2
80 2
90 1
97 2
9 2
29 2
98 2
47 1
61 1
32 1
3 1
76 2
4 2
8 2
3 2
73 2
76 2
12 1
78 1
35 1
50 2
62 2
12 1
10 1
25 1
66 1
45 1
3 2
77 1
38 2
83 2
79 1
69 1
20 2
20 1
25 1
98 2
87 2
97 2
80 1
61 1
94 2
52 1
52 2
89 1
79 2
7 2
72 1
50 2
89 2
38 2
74 2
31 1
50 2
21 1
42 1
70 1
54 2
32 2
10 2
94 1
14 2
78 1
65 1
44 1
78 1
58 1
80 1
43 1
76 1
57 1
4 2
70 1
26 1
57 1
54 1
58 2
8 1
63 2
61 1
61 2
23 1
35 2
96 1
9 1
32 1
71 1
61 2
62 1
99 2
35 1
47 2
100 2
28 1
32 1
89 1
27 1
66 1
24 2
1 2
52 2
86 2
64 2
38 2
63 1
33 1
35 2
50 1
84 2
83 2
84 2
97 2
80 2
53 1
79 2
32 2
82 2
24 1
68 2
15 1
3 1
99 2
95 1
43 2
25 2
25 1
19 2
60 2
46 1
8 1
55 2
48 1
54 2
27 2
84 1
59 2
64 1
70 1
17 1
65 2
21 1
41 2
33 2
11 2
95 2
28 2
68 2
34 1
72 2
26 1
6 1
66 1
9 1
65 1
35 2
76 1
51 2
100 2
58 1
5 2
81 1
49 1
2 1
29 1
56 1
87 1
100 2
53 2
82 1
9 1
51 2
66 1
43 1
69 1
22 2
91 2
75 2
50 2
9 2
34 2
78 2
54 2
29 2
64 1
10 1
97 1
63 2
76 2
9 1
97 1
21 1
36 1
29 2
47 1
38 2
37 2
54 1
8 2
16 1
30 2
39 1
38 1
37 1
77 1
74 1
35 1
15 2
5 1
75 2
2 2
67 2
85 1
52 1
73 2
59 1
8 1
60 2
76 1
36 1
91 1
80 1
12 1
65 2
14 1
65 1
13 1
77 2
47 1
57 2
80 2
81 2
77 2
13 1
30 2
56 2
34 2
16 1
27 1
93 2
6 1
31 1
20 1
16 2
50 1
31 1
34 1
74 1
10 2
90 2
96 2
92 2
47 2
26 1
57 2
92 2
14 1
21 2
72 1
93 1
15 2
91 1
78 1
62 1
35 2
27 2
7 1
6 1
94 1
63 1
82 1
51 1
29 2
31 1
88 1
86 2
49 2
66 1
33 2
33 1
71 2
49 2
39 2
57 2
26 2
97 1
93 2
92 2
32 2
41 1
33 1
37 1
85 1
34 1
27 1
43 1
94 2
90 2
8 2
6 2
24 2
50 1
19 1
69 1
26 1
80 1
75 1
88 1
15 1
25 1
23 2
44 1
37 1
71 1
69 1
39 1
23 1
56 1
99 2
37 1
44 2
22 1
57 2
45 1
50 1
13 1
65 2
24 2
92 1
93 1
54 1
49 1
48 1
69 1
42 1
11 1
2 1
28 1
64 1
83 1
62 2
92 1
66 1
35 1
74 2
38 1
100 1
24 2
50 2
20 1
35 1
13 1
11 2
7 1
87 2
38 1
48 1
37 1
18 1
26 2
88 1
76 2
51 1
20 1
2 1
25 1
71 1
90 2
71 2
49 1
91 1
82 2
28 2
4 2
48 1
79 2
29 2
85 2
94 1
90 2
4 2
15 1
82 1
94 1
44 1
28 1
16 2
50 1
10 1
33 1
61 1
11 2
86 1
31 2
21 1
52 1
75 1
40 2
75 1
69 2
7 2
31 1
73 1
12 1
60 2
11 1
33 1
3 1
3 1
92 1
34 2
92 1
63 1
27 1
67 1
99 1
3 1
61 1
18 1
36 1
5 1
44 2
83 2
2 1
79 2
66 1
71 1
92 1
38 2
88 1
9 2
28 1
25 2
40 1
44 1
20 1
59 1
52 2
3 1
83 2
7 1
96 1
48 2
2 1
25 1
83 2
34 1
68 1
32 2
3 2
55 1
97 1
62 2
33 2
26 1
28 1
70 2
74 1
54 1
5 1
11 2
56 2
9 2
63 2
98 1
34 1
90 1
31 2
76 2
40 1
92 2
12 1
41 1
76 2
85 2
81 2
70 1
100 2
11 1
90 2
91 2
33 1
2 2
18 1
22 1
5 2
80 2
10 1
83 1
94 1
76 2
41 2
66 1
53 1
60 2
23 1
41 1
16 2
78 2
23 1
11 2
12 1
47 1
64 1
53 2
100 2
39 1
99 1
56 2
40 1
47 2
35 1
93 2
79 2
19 1
72 2
76 2
58 2
20 1
13 2
26 2
18 2
59 1
98 1
56 1
34 1
68 1
67 2
57 2
38 2
61 2
59 2
12 1
89 1
36 1
65 2
7 2
52 1
28 1
14 1
1 2
53 2
64 1
57 2
97 1
53 1
83 1
10 1
1 1
67 2
2 1
56 2
88 1
23 2
10 2
91 2
88 1
3 2
51 1
11 1
1 1
5 2
37 1
83 1
15 2
70 1
39 1
58 1
52 2
97 2
80 2
1 2
32 1
34 2
12 2
64 1
80 1
52 1
85 2
100 2
87 1
92 2
3 1
40 1
8 1
63 2
82 1
53 1
46 2
16 1
12 2
51 2
38 1
71 2
92 2
87 1
37 2
8 1
25 2
36 1
87 2
86 2
41 2
49 1
29 2
100 1
19 1
42 2
36 1
87 1
69 2
31 1
44 1
9 2
78 2
47 1
10 1
48 2
17 1
30 1
70 2
81 1
8 2
68 1
58 2
74 2
30 2
20 1
77 1
37 2
41 1
74 2
24 2
83 2
77 2
33 1
21 1
45 2
27 1
29 1
43 1
54 1
95 2
38 1
63 1
79 2
3 2
79 1
34 2
37 2
33 1
24 1
49 2
87 2
37 2
57 1
92 2
34 2
97 1
5 2
19 1
43 1
87 2
63 2
64 1
40 2
35 1
41 2
87 2
87 2
34 1
48 2
28 1
65 1
40 2
73 2
52 1
13 1
66 1
87 2
69 1
71 1
5 1
14 1
18 2
73 2
57 1
98 2
96 2
53 2
99 1
90 1
95 2
61 1
12 1
14 2
54 2
22 2
43 1
81 2
23 1
89 2
83 2
35 2
67 1
81 2
94 2
72 1
4 2
3 1
44 1
71 2
54 1
73 2
54 1
69 2
33 2
27 2
67 2
87 1
70 2
53 2
51 1
67 1
58 1
75 1
82 1
52 1
58 1
80 1
49 1
9 1
41 2
64 1
70 1
15 1
57 1
17 1
35 2
56 1
94 1
93 1
92 1
16 2
81 1
19 2
86 2
67 2
30 1
90 1
92 1
73 1
35 1
5 1
21 2
49 1
7 1
22 2
11 1
87 1
92 2
46 1
86 2
2 2
5 1
10 2
40 1
22 1
5 1
65 2
23 2
59 2
14 2
76 2
54 2
89 2
54 1
33 2
87 1
42 1
66 2
17 1
30 2
51 2
58 2
29 1
29 2
63 1
58 2
53 1
35 1
10 2
52 1
68 1
65 2
47 2
96 1
77 1
88 1
14 1
7 2
74 1
100 2
3 2
4 1
63 2
50 2
6 2
98 1
23 1
68 2
9 2
76 2
80 2
39 2
33 2
59 1
62 2
8 2
21 2
12 1
36 2
100 1
97 1
23 2
83 2
50 1
52 1
73 1
92 1
58 1
95 2
7 2
