TEST DATA FOR `charm'

Input for test 1

4 6
1 4
2 6
3 12
2 7

Output for test 1

23

Input for test 2

5 10
8 74
3 32
8 49
8 98
3 17

Output for test 2

98

Input for test 3

32 82
60 79
26 11
76 46
11 24
30 6
76 92
48 7
56 64
59 77
74 96
66 1
9 38
61 54
40 9
30 35
73 86
43 99
63 6
13 57
74 98
30 4
34 35
14 84
5 55
26 81
25 41
63 28
30 61
80 58
78 26
61 8
60 91

Output for test 3

339

Input for test 4

293 801
166 25
157 60
139 97
16 12
352 49
67 78
181 95
169 49
379 8
93 89
218 92
388 63
66 46
221 83
118 88
96 59
71 10
400 76
220 42
1 80
67 55
122 80
383 50
219 4
156 57
299 78
309 94
47 34
363 34
133 15
18 57
356 51
246 45
348 64
220 72
359 41
31 39
299 60
302 39
49 69
237 51
23 69
42 73
140 65
7 16
169 84
278 27
223 95
269 31
62 41
32 85
61 68
236 38
98 64
271 100
13 54
346 24
143 53
285 89
57 75
302 9
75 56
31 23
123 34
168 1
186 95
353 49
14 88
340 100
194 15
266 66
173 38
266 28
61 76
188 8
261 70
371 88
220 36
384 64
386 68
392 32
179 85
331 37
76 66
275 99
158 65
215 55
86 11
44 85
363 4
123 18
107 59
310 97
282 85
342 98
351 37
95 51
62 71
40 46
323 60
215 54
342 93
188 67
284 17
197 55
309 32
352 78
400 77
207 93
188 9
317 70
68 34
322 74
294 26
390 77
350 26
91 2
140 92
272 34
46 41
128 59
341 4
27 24
101 67
15 54
340 54
219 68
398 83
303 32
365 68
266 92
31 91
74 69
17 91
326 80
68 97
158 24
207 80
323 3
176 72
92 24
98 75
328 11
100 44
262 42
306 80
309 26
308 76
210 88
303 79
223 35
233 57
151 87
113 13
306 71
393 90
184 27
343 21
347 4
127 86
124 59
120 53
320 93
242 97
219 25
170 61
370 59
266 86
158 12
286 74
130 14
61 36
277 4
302 77
50 35
102 86
338 66
143 8
101 28
98 98
43 45
162 8
315 20
294 17
64 67
368 84
175 35
118 63
306 33
53 36
92 53
3 2
202 59
107 47
330 32
280 72
156 91
115 50
36 77
298 27
49 21
20 96
303 59
362 94
116 69
91 21
21 71
34 59
298 61
344 86
66 58
307 21
240 2
230 58
109 26
256 58
44 95
153 88
264 15
26 15
286 60
170 41
66 57
92 19
36 29
92 9
291 87
43 90
400 39
324 64
162 44
387 36
10 35
176 98
222 25
305 77
8 89
12 97
100 56
237 65
106 97
333 7
77 55
162 47
358 57
255 80
215 99
89 41
14 42
269 72
21 74
216 56
224 94
90 9
1 91
349 62
33 10
150 43
396 72
64 44
388 77
109 50
296 58
173 65
315 14
69 64
179 91
19 22
226 7
280 19
382 97
384 34
247 90
396 96
155 79
240 3
219 14
364 99
142 57
186 29
66 55
381 32
18 1
368 74
304 74
177 93
312 35
222 24
55 98
96 33
267 11
71 8
92 2

Output for test 4

2159

Input for test 5

423 2311
164 33
144 70
75 76
67 95
236 26
222 64
369 91
89 10
130 13
117 38
305 58
187 78
26 61
90 15
156 7
371 59
253 57
96 52
233 37
198 99
211 31
49 77
340 79
20 73
241 20
71 77
201 59
387 39
74 59
242 13
138 38
173 81
289 79
16 44
142 31
362 58
206 78
399 34
269 6
23 12
362 68
382 29
54 39
274 27
197 56
152 84
182 81
169 87
264 5
128 28
317 97
220 1
285 45
41 90
67 6
348 65
145 14
105 91
264 68
138 11
85 24
42 45
309 26
94 39
47 6
60 40
298 79
193 97
3 49
140 62
310 43
179 18
327 63
39 96
137 47
170 24
270 23
389 34
338 89
10 34
154 28
282 66
302 50
78 28
215 64
386 75
149 98
218 53
131 20
193 79
27 35
275 89
83 16
199 27
213 43
214 96
28 98
253 76
97 44
315 54
240 44
73 63
307 62
166 85
279 61
77 86
3 91
237 29
270 6
355 24
309 92
141 77
31 61
292 34
112 27
90 12
183 89
363 55
144 92
98 51
203 53
6 91
47 83
17 60
72 52
238 49
322 16
57 46
134 13
175 31
176 59
88 94
212 19
311 98
219 68
331 97
76 3
28 68
392 20
9 81
152 9
214 16
144 53
157 87
326 64
244 2
98 5
94 66
195 96
68 80
132 5
394 14
240 56
270 65
183 55
231 26
394 41
192 11
120 59
49 74
124 92
40 74
274 37
31 69
298 40
245 85
240 83
81 62
251 16
110 26
284 98
271 24
343 65
56 41
81 8
42 72
192 38
258 82
125 83
254 55
335 9
56 45
265 16
17 50
122 23
362 30
3 8
168 27
119 62
162 100
174 62
20 6
268 85
217 28
173 66
80 5
79 64
28 34
186 47
301 16
384 49
286 68
361 100
46 38
375 23
112 96
59 80
120 53
2 74
259 3
345 91
369 90
332 95
279 44
4 80
257 39
349 50
17 35
88 22
291 3
324 62
388 1
300 9
199 3
93 12
60 53
317 27
348 7
148 47
170 15
197 38
275 70
380 37
213 70
155 46
73 14
20 63
267 60
136 100
298 52
348 15
262 8
82 24
80 58
19 87
325 43
260 61
350 89
373 7
327 2
237 39
13 70
288 91
204 22
231 18
305 58
32 39
34 55
153 40
382 5
18 83
23 41
321 22
310 73
240 86
94 46
109 42
395 46
131 40
77 37
211 67
209 20
341 51
342 75
8 96
381 68
295 27
158 82
44 94
351 8
212 39
44 6
174 28
327 26
172 48
314 59
383 11
351 36
372 85
344 22
153 35
124 5
137 58
373 85
214 23
53 97
335 87
31 31
127 67
40 44
375 42
80 29
236 20
266 76
8 39
312 66
29 24
24 23
184 40
158 97
3 66
105 13
183 91
383 73
349 73
141 80
207 60
345 67
325 99
331 30
306 56
60 81
346 45
163 81
400 34
128 11
124 23
113 55
180 49
275 1
234 63
5 78
270 88
12 27
138 50
397 81
393 45
305 97
57 35
28 21
2 29
59 74
62 35
316 49
320 55
321 15
48 85
312 7
382 87
121 76
145 8
22 44
277 93
343 86
153 22
101 86
354 60
308 43
392 85
182 40
107 67
381 16
126 69
337 48
322 35
323 31
232 22
99 33
154 9
245 33
99 98
289 75
211 95
391 22
375 56
118 45
297 47
1 78
395 43
176 28
228 47
222 16
317 9
78 99
32 61
175 24
308 91
204 83
320 4
137 50
241 97
56 88
244 2
58 78
31 69
121 73
59 23
189 90
145 36
181 87
261 44
226 17
30 81
286 69
386 89
15 73
356 44
349 92
259 2
235 23
256 53
183 15
307 69
249 78
71 95
22 69
368 48
182 49
96 9
367 14
192 11
27 59
267 50

Output for test 5

4713

Input for test 6

551 3488
146 34
205 38
110 32
51 7
118 55
310 36
61 9
356 4
177 16
5 10
138 6
19 18
64 41
129 56
397 54
124 24
62 2
159 22
24 59
146 72
120 93
273 94
194 13
202 86
321 46
204 34
294 6
246 63
330 68
386 46
6 19
2 70
258 96
366 47
171 93
147 39
347 11
393 29
188 75
88 31
51 38
41 82
34 26
125 37
320 74
25 71
124 34
335 91
13 8
237 53
151 9
300 48
149 71
223 55
242 66
52 85
306 33
156 7
41 70
133 16
210 15
59 7
260 22
246 59
83 93
190 36
194 81
13 74
370 74
118 47
17 82
264 47
312 20
134 6
312 74
248 47
222 36
150 52
120 33
385 81
273 81
279 42
4 20
72 10
353 79
153 92
156 39
14 5
180 91
375 70
288 32
165 58
171 83
92 42
334 77
37 90
113 83
352 1
36 94
304 27
303 24
12 83
66 63
392 84
318 3
375 6
324 36
252 85
93 45
357 36
366 90
22 47
52 29
316 34
206 3
82 70
13 94
43 7
195 45
59 31
246 11
35 47
291 89
260 52
116 65
311 18
200 87
396 30
148 99
335 92
231 40
280 40
139 93
90 71
192 98
320 3
224 3
192 27
308 35
370 66
191 81
309 59
15 39
340 33
79 87
336 71
209 6
69 13
236 65
289 21
340 74
91 97
282 11
161 51
209 60
388 71
288 43
247 7
42 40
52 39
249 57
250 55
22 7
360 39
157 19
40 2
87 85
154 84
63 21
106 25
345 9
87 6
41 51
397 28
2 95
25 24
208 34
358 41
178 5
95 78
204 94
146 7
242 81
122 83
69 59
30 86
311 76
96 33
55 72
302 74
327 2
332 21
184 83
367 89
287 58
379 24
239 36
319 66
271 38
280 39
118 80
380 85
216 10
326 63
274 79
351 13
167 53
98 15
313 32
208 49
164 5
260 54
349 20
265 32
62 96
140 45
8 26
78 77
278 92
150 53
397 74
215 77
372 31
167 7
182 71
341 27
172 48
352 77
76 75
133 4
381 11
281 56
191 92
170 59
155 30
126 3
164 22
358 69
69 22
368 3
84 1
199 13
191 75
107 2
1 53
135 38
212 58
84 65
249 59
95 20
209 26
262 21
91 74
22 100
208 22
376 69
173 63
136 51
224 75
126 1
283 6
336 6
368 44
365 57
183 38
379 33
102 54
230 92
64 8
272 75
305 72
368 14
133 7
307 85
33 5
126 5
361 9
20 39
1 76
307 28
311 77
336 64
126 21
125 10
397 46
324 12
153 70
71 46
347 53
258 24
13 42
340 79
8 87
14 18
183 37
78 89
366 82
209 19
263 32
366 17
340 1
132 9
329 20
9 43
387 81
246 2
293 86
171 41
353 88
199 48
376 15
154 24
11 99
313 12
382 36
147 4
248 93
251 45
75 63
346 6
195 20
75 49
272 55
287 59
245 58
374 80
379 46
330 41
155 10
212 69
163 84
230 23
11 93
373 35
366 32
322 25
189 63
48 55
387 21
362 84
191 68
307 24
366 5
230 74
82 92
104 49
161 58
284 54
333 48
326 4
361 99
80 26
62 82
249 53
317 46
265 69
42 41
339 93
396 9
312 80
183 90
241 14
198 23
171 85
281 19
146 29
233 47
302 33
98 70
337 85
218 54
93 22
239 27
373 52
19 76
369 84
100 48
154 98
87 40
174 54
82 5
227 94
187 27
224 5
393 79
63 98
386 10
44 48
18 80
228 99
155 90
120 18
75 60
307 36
95 7
373 97
181 92
128 16
256 40
258 97
185 89
308 9
363 27
344 13
371 87
360 39
254 21
107 15
108 78
372 94
128 64
166 53
357 69
258 79
282 13
204 91
286 73
43 15
64 82
215 11
369 95
357 99
152 55
275 95
322 37
321 52
263 16
135 91
299 76
235 44
284 92
56 49
33 92
203 63
348 64
86 50
235 89
205 39
395 78
54 95
338 39
140 91
400 30
58 78
235 30
106 63
198 32
12 41
136 84
290 64
12 27
56 33
183 69
119 92
53 67
140 3
255 56
359 33
52 49
62 78
222 69
242 74
12 2
265 93
38 86
289 76
229 77
392 68
10 85
355 7
217 41
160 36
238 86
10 86
72 72
330 91
294 73
109 97
76 86
5 7
386 46
106 18
203 62
284 63
47 56
378 31
179 11
46 17
117 33
201 43
104 56
341 17
67 20
94 4
196 9
203 3
4 75
332 65
275 100
240 61
71 62
12 71
91 96
90 92
391 42
308 78
375 89
272 70
2 100
221 8
114 42
399 38
377 82
118 69
246 1
320 54
366 13
356 16
308 40
309 60
39 50
192 7
12 81
327 7
123 71
320 7
369 49
81 40
245 53
378 60
345 41
28 34
351 87
268 32
20 83
92 32
143 100
235 41
101 19
225 13
400 82
276 58
136 2
63 18
96 13
109 71
219 20
40 30
164 59
226 7
159 49

Output for test 6

5910

Input for test 7

653 6572
242 49
254 7
147 96
153 16
242 7
129 89
373 67
366 35
82 3
133 64
232 100
220 79
68 50
74 9
387 83
75 63
318 87
24 50
129 60
185 43
48 83
240 6
205 12
211 17
207 74
285 78
200 57
86 21
282 35
32 65
181 15
4 39
125 58
344 93
330 57
65 92
206 97
119 28
301 27
119 10
51 96
381 50
398 33
388 37
289 44
355 88
210 33
13 43
30 24
168 85
198 11
46 7
77 90
385 30
29 37
58 25
288 92
51 52
10 92
256 20
126 22
170 24
203 27
204 20
373 35
353 45
310 71
40 95
214 63
161 72
326 19
226 46
379 62
375 18
27 56
23 61
374 29
158 70
190 40
308 80
243 43
298 75
18 45
236 7
169 4
388 48
5 93
43 75
369 27
142 8
189 30
238 58
111 49
28 81
25 98
386 78
157 4
90 83
325 25
366 93
61 100
116 87
346 15
26 76
302 5
139 17
49 42
223 40
330 36
268 66
93 81
139 29
47 18
378 93
193 59
205 6
89 15
359 36
170 30
367 57
235 32
60 96
376 57
382 50
220 21
363 78
200 70
201 83
359 61
167 85
89 17
332 79
221 54
127 87
399 33
400 62
261 6
232 19
285 5
50 39
93 59
81 89
49 30
31 35
54 47
326 8
157 94
122 43
222 89
25 94
290 79
367 3
346 89
362 57
311 83
288 21
379 37
36 66
294 71
207 95
122 86
227 24
26 23
390 29
256 79
17 38
361 11
83 86
168 29
306 7
399 71
222 28
71 20
117 23
378 42
102 87
398 73
92 33
54 12
82 6
235 39
372 70
195 33
286 96
363 32
257 20
243 26
335 41
36 63
383 84
156 6
366 19
295 70
72 23
197 95
6 97
129 20
370 6
130 2
92 64
185 63
154 91
150 81
92 14
176 56
239 15
299 49
4 78
34 23
235 100
319 9
215 37
237 21
184 9
227 62
343 94
169 95
111 37
235 30
120 75
252 38
71 68
82 71
238 90
188 69
86 45
129 79
25 15
12 24
127 10
326 99
244 82
399 81
65 50
154 17
331 16
163 39
363 95
353 100
176 10
134 80
198 53
155 41
94 48
43 57
279 28
181 43
306 80
195 87
48 32
367 4
186 66
285 98
70 78
286 1
74 79
13 91
168 97
348 59
327 38
201 73
272 16
280 80
175 65
191 31
73 98
334 52
112 52
66 9
76 21
118 5
385 8
391 74
289 72
118 88
243 73
133 77
254 18
347 24
362 42
242 94
250 79
244 78
258 38
279 33
312 60
66 29
16 28
240 93
351 68
8 30
381 100
325 43
21 47
127 86
65 61
114 39
111 73
77 26
396 60
333 47
347 45
29 19
371 69
214 100
152 20
394 32
147 44
313 95
118 69
253 10
87 70
6 97
164 8
198 3
375 27
45 59
56 24
272 83
192 6
242 19
337 88
222 86
311 2
258 84
314 20
198 11
253 63
264 58
262 52
86 47
110 36
63 57
145 9
93 47
196 30
26 64
152 14
377 62
354 83
78 5
39 17
307 69
316 87
104 30
197 31
195 51
125 35
354 25
358 48
273 100
109 93
245 51
320 10
287 46
49 22
333 34
203 9
114 31
164 36
355 17
311 96
342 17
34 7
144 89
349 65
308 68
289 67
268 44
42 23
354 12
294 33
274 97
176 22
342 71
316 99
392 46
326 97
41 67
375 9
319 38
228 16
225 68
151 87
177 91
311 24
23 97
192 51
47 50
142 37
380 51
123 95
294 19
198 10
152 85
381 19
85 70
169 15
380 95
387 9
92 93
150 89
82 14
174 1
55 8
223 68
255 47
253 72
394 21
392 67
83 21
306 47
82 15
99 69
239 91
375 39
214 68
370 88
195 62
165 56
79 68
175 79
73 75
82 84
53 45
169 39
307 18
86 54
157 77
52 84
341 49
190 91
163 48
249 74
268 80
199 33
351 93
248 87
353 75
168 32
225 76
107 22
20 3
150 29
400 63
190 86
47 86
205 9
234 65
129 87
247 95
77 64
397 84
227 11
238 5
36 93
44 94
227 80
136 5
181 77
28 23
304 9
67 66
95 18
356 77
136 35
151 13
271 14
222 17
31 10
192 88
243 95
11 31
355 87
204 34
14 69
334 80
172 95
373 91
228 47
161 79
19 19
132 3
277 74
71 65
93 64
179 65
148 99
391 48
87 25
265 84
85 97
296 72
200 64
94 26
54 66
358 50
310 16
379 33
202 92
126 83
103 41
324 11
373 16
219 72
192 85
243 4
23 96
233 81
129 100
395 13
92 7
18 98
201 7
241 87
214 91
384 83
327 13
255 49
164 29
308 50
24 24
265 90
386 65
131 79
3 99
137 6
109 97
364 27
348 73
393 39
20 22
75 71
90 57
134 23
239 64
76 56
353 19
114 39
147 59
19 53
25 39
119 93
97 73
72 7
388 27
232 14
198 92
45 72
34 95
365 88
140 50
367 24
227 80
15 34
121 85
207 56
270 11
107 56
244 8
277 76
181 19
304 91
377 44
299 14
346 34
188 39
276 30
94 33
46 69
159 84
136 57
378 31
71 66
42 97
98 22
285 23
174 73
364 11
54 5
96 12
354 40
151 58
59 78
77 10
254 62
351 100
160 64
141 62
77 36
30 11
330 2
204 21
275 1
73 15
261 81
8 94
96 100
273 20
343 47
296 96
261 25
397 20
355 95
40 100
383 56
120 31
92 4
263 42
261 42
123 86
280 27
130 39
57 37
81 93
350 27
353 24
176 43
223 74
294 73
25 16
125 70
61 11
167 78
260 7
300 89
395 34
398 61
252 59
77 3
339 11
97 46
136 56
368 40
325 100
313 58
372 25
352 38
39 86
120 53
102 29
189 36
155 70
110 55
193 79
29 21
248 39
115 64
96 43
239 72
352 94
11 42
69 40

Output for test 7

8470

Input for test 8

1833 8501
11 64
388 29
170 28
193 6
315 90
243 94
369 21
95 52
235 38
141 68
12 43
357 90
145 62
63 82
20 59
193 34
369 16
185 44
127 70
105 4
8 83
383 73
136 55
287 40
99 98
330 24
336 60
162 70
356 39
89 97
374 24
53 23
323 82
168 4
324 26
318 91
366 76
148 68
67 61
63 12
232 42
159 42
311 27
55 36
238 65
130 27
46 67
147 57
373 6
274 80
373 50
149 55
244 15
209 34
60 74
118 21
167 31
372 28
12 96
362 30
52 50
289 7
19 47
232 33
43 30
200 36
67 36
29 57
343 24
384 24
226 92
32 10
72 9
207 63
369 89
55 3
46 29
69 31
222 81
341 22
255 9
30 23
221 46
115 12
209 22
165 38
6 70
55 51
152 63
65 65
112 24
177 26
20 78
254 70
263 89
294 58
9 18
386 15
352 44
355 52
207 43
199 23
358 12
183 87
59 81
196 1
33 55
393 11
339 50
256 52
128 52
195 42
370 86
305 15
189 57
193 19
233 7
151 57
29 22
338 24
105 87
5 5
389 83
99 2
210 92
332 71
276 68
132 27
367 32
228 91
12 49
126 52
199 92
330 73
118 65
234 12
95 77
179 46
38 88
272 60
219 84
76 47
111 29
72 19
195 25
310 94
28 22
94 97
66 50
87 84
309 84
345 82
352 24
237 6
300 31
267 19
113 53
175 8
239 87
146 55
325 41
260 3
183 28
133 16
45 37
388 36
197 15
164 74
362 98
96 1
163 66
152 48
59 16
41 42
306 43
332 97
329 55
85 45
198 7
254 18
342 76
349 62
292 76
360 14
19 45
261 19
210 38
2 76
343 93
308 62
217 27
136 6
400 22
373 47
43 34
184 79
273 38
350 71
109 41
230 94
86 74
33 97
286 80
325 18
138 48
5 32
147 3
68 29
194 93
279 67
248 5
342 2
134 56
311 31
336 92
243 86
55 22
335 15
296 99
241 72
326 11
191 15
321 61
304 70
365 22
244 52
235 14
264 55
23 55
145 93
89 61
288 67
20 15
167 32
335 63
3 18
177 13
274 89
391 33
359 72
227 9
27 75
98 77
273 46
225 22
181 3
250 37
204 86
356 4
72 36
354 73
68 80
87 9
383 72
182 98
342 77
100 34
260 98
1 52
194 82
155 83
149 60
284 79
17 25
210 6
25 38
351 39
102 98
174 17
25 16
33 18
12 9
186 23
125 18
219 1
112 66
57 22
147 62
341 84
68 10
190 14
346 77
105 42
148 58
133 39
6 22
112 48
232 25
139 7
147 41
9 44
184 75
63 10
169 92
44 61
35 24
274 14
229 73
236 98
120 30
144 2
219 11
122 90
210 94
347 17
311 29
312 60
82 75
5 81
10 94
152 64
252 56
318 72
93 88
397 5
261 73
243 80
311 20
378 15
343 40
322 70
97 81
88 85
298 17
190 2
136 99
117 28
323 60
175 27
354 35
9 100
327 41
351 36
214 59
81 28
54 20
398 85
237 94
88 46
276 77
129 4
127 28
109 70
33 53
21 50
13 99
112 90
135 58
353 45
344 89
163 11
22 60
139 96
393 42
253 95
7 69
230 8
91 51
139 82
347 10
292 15
75 3
165 98
42 91
47 32
81 58
123 90
212 21
45 95
151 51
149 91
59 98
239 98
48 21
57 98
316 14
223 38
371 80
370 87
378 94
341 3
306 58
240 99
295 39
383 73
339 83
236 62
252 3
249 100
280 63
230 53
72 93
398 18
22 2
128 90
21 56
310 82
219 53
172 61
266 83
107 86
68 13
167 28
384 26
57 11
58 49
311 6
112 12
312 52
101 11
35 20
314 10
314 36
221 11
136 61
258 85
99 19
84 29
320 9
398 69
289 26
136 9
284 71
291 60
331 56
332 97
4 94
136 52
174 24
268 13
73 41
151 97
113 85
252 11
366 73
194 89
276 12
15 40
393 97
299 81
269 52
3 92
121 29
311 19
198 14
298 73
197 87
376 15
27 7
151 37
265 91
91 75
86 95
176 55
159 63
239 9
367 66
99 4
38 52
363 75
73 35
123 22
319 41
110 27
5 48
192 71
299 25
131 56
123 80
290 19
275 28
300 43
86 93
54 67
295 86
221 65
216 97
198 15
163 94
277 37
160 19
262 75
338 15
25 2
75 88
386 28
378 81
120 25
98 67
128 34
172 51
261 67
172 42
251 97
61 15
332 4
335 32
78 6
131 8
349 54
222 30
5 83
122 53
53 60
96 2
1 81
282 33
307 11
284 65
396 87
230 62
249 60
184 34
268 34
45 84
388 39
105 90
310 99
113 41
122 40
202 42
185 59
92 77
158 9
6 65
103 32
31 17
301 48
164 86
375 42
19 22
16 22
349 56
176 6
139 75
77 9
190 74
66 54
174 44
280 37
290 68
48 72
216 10
35 28
33 25
373 60
163 65
230 43
248 49
43 98
81 4
340 29
316 54
351 99
193 91
30 39
214 78
230 70
354 74
242 13
259 67
308 64
387 26
125 83
102 5
148 59
105 34
48 88
348 97
151 87
29 16
31 76
84 2
154 66
36 77
126 73
134 95
262 18
63 88
116 24
116 58
117 49
337 69
396 15
215 79
72 42
226 29
91 96
378 2
95 90
71 94
265 58
395 88
30 85
315 48
4 39
55 70
137 62
223 18
267 35
57 1
336 89
381 82
65 61
364 19
21 91
261 48
364 2
157 32
328 71
349 58
87 62
263 66
291 37
166 97
364 19
282 71
112 83
58 28
270 82
158 22
393 35
355 95
13 41
351 79
106 46
11 11
320 2
225 15
269 59
58 99
32 90
237 37
281 32
42 44
33 13
60 43
231 18
392 87
230 6
267 86
199 94
381 10
116 36
104 12
43 92
77 59
182 15
81 48
206 89
123 76
197 59
128 21
257 47
226 59
6 41
212 90
284 40
196 97
192 36
226 17
120 17
383 90
105 60
66 67
333 27
11 46
164 40
224 34
101 30
25 10
42 88
67 79
165 7
309 68
267 87
324 82
357 1
290 9
382 24
233 3
8 91
383 90
87 65
312 50
181 42
370 7
286 2
363 97
377 52
380 27
395 32
341 41
355 55
320 34
90 32
303 98
320 29
272 54
4 69
14 56
53 99
118 74
254 26
52 34
306 32
400 47
153 7
189 92
14 48
139 81
105 25
390 40
150 98
176 16
121 56
23 14
229 1
261 10
364 3
394 57
37 39
47 65
269 9
272 33
66 90
181 13
297 92
310 25
59 62
309 73
40 3
378 86
72 94
360 92
48 51
353 29
116 81
73 71
96 48
156 99
378 76
352 11
23 99
107 41
185 42
178 52
330 73
195 92
351 90
169 10
69 58
94 66
234 21
331 52
332 35
9 45
215 12
14 81
114 77
379 8
358 77
101 85
243 94
248 38
276 13
236 78
30 59
392 80
232 64
224 16
383 56
187 35
290 76
254 87
160 88
218 43
247 36
50 5
178 35
223 72
398 3
88 82
84 28
150 60
29 6
198 67
179 77
389 77
370 86
242 27
82 57
153 71
114 28
34 13
293 56
17 16
379 39
199 9
229 44
224 44
262 23
58 78
225 36
159 61
257 94
255 21
212 88
307 61
398 73
203 60
248 55
99 19
236 30
345 7
204 76
150 27
256 35
326 2
101 73
157 49
344 79
8 58
58 32
352 24
316 73
103 7
317 88
331 92
52 20
134 23
186 51
390 53
309 94
20 75
13 35
376 59
336 76
42 46
370 58
284 17
82 36
45 87
21 85
245 63
360 55
325 79
72 30
277 54
97 57
283 75
383 31
327 3
339 5
18 14
295 60
195 17
151 5
19 60
123 35
176 9
193 77
327 27
359 66
267 66
202 86
24 59
83 55
177 30
130 26
74 37
238 68
60 5
78 42
337 63
160 80
254 15
209 70
83 33
29 81
310 93
157 23
211 58
321 55
244 13
383 3
280 97
205 7
126 11
1 7
211 46
127 62
258 7
285 35
132 46
11 17
113 51
17 97
182 62
366 86
253 38
76 94
370 65
255 52
116 76
146 5
55 22
96 91
122 8
180 21
62 99
59 4
324 55
43 8
202 40
123 90
146 43
265 39
352 35
33 28
234 76
147 24
135 82
394 62
99 75
269 78
338 86
8 11
18 91
312 43
38 69
149 71
254 62
30 89
209 62
14 9
183 53
389 31
136 36
110 86
388 58
145 76
115 81
36 5
288 28
42 63
182 100
121 97
224 11
383 26
79 65
227 65
383 19
372 73
275 17
165 85
14 32
98 33
38 26
117 93
151 16
45 23
294 12
338 90
103 82
362 19
317 24
287 6
10 64
295 28
138 10
313 87
368 59
59 20
218 62
68 85
159 21
93 77
287 22
81 52
183 85
277 80
40 47
111 73
30 31
60 65
253 46
295 93
3 25
213 73
396 34
397 24
314 54
208 98
240 84
209 71
204 89
343 50
359 32
340 25
244 6
296 50
196 13
134 40
92 96
284 74
89 31
141 43
92 28
72 86
146 26
206 69
107 10
70 90
87 95
251 75
150 64
2 64
228 47
181 39
336 60
95 51
116 9
301 94
382 15
352 3
90 93
270 27
157 14
234 96
136 99
159 24
198 33
215 65
272 25
301 8
339 83
393 38
108 41
270 93
326 28
160 85
261 22
248 49
214 48
10 21
392 40
129 37
63 24
294 62
7 46
2 74
237 51
142 56
205 50
264 51
62 98
12 82
202 22
18 14
367 93
277 29
75 44
367 25
126 64
223 39
316 15
122 85
378 29
93 58
330 80
339 9
391 95
128 80
284 91
314 53
323 52
103 39
183 14
316 68
356 3
341 82
246 6
245 74
274 1
23 92
47 41
208 61
334 18
235 47
19 31
199 22
156 47
183 20
219 90
245 34
3 24
286 60
117 40
74 43
198 31
236 25
5 87
52 94
7 47
307 60
202 100
179 100
213 62
263 60
195 61
335 50
303 23
160 8
156 36
144 96
44 2
348 89
364 76
128 93
202 63
9 61
290 72
365 82
375 90
322 98
126 86
255 70
388 1
119 71
62 74
80 95
47 83
330 89
397 67
172 81
77 14
271 91
12 26
285 93
84 26
139 26
4 71
240 87
197 14
178 38
110 35
207 59
357 64
32 29
289 92
395 21
346 74
385 50
207 38
131 3
114 65
213 43
55 54
260 41
208 40
39 42
385 55
296 90
72 22
162 4
101 59
274 48
191 27
10 40
305 16
60 63
318 46
266 2
277 43
283 82
165 10
339 59
346 51
58 46
327 65
158 6
131 42
147 63
66 53
311 35
230 27
136 35
315 1
312 91
264 64
241 22
225 47
317 57
128 64
392 29
49 90
305 99
55 2
187 64
222 39
8 25
145 70
318 48
144 50
95 8
309 65
283 40
300 74
103 54
173 73
362 35
154 31
342 6
244 84
189 34
333 90
152 95
220 42
297 51
280 98
302 79
396 28
325 79
215 30
227 29
194 25
137 8
22 22
333 68
269 51
339 62
29 67
220 80
246 48
172 88
394 86
140 63
68 32
301 94
76 50
147 30
74 41
62 57
12 38
399 13
391 97
385 33
140 21
123 47
67 6
173 64
287 35
286 2
181 29
99 100
237 61
400 45
99 30
82 84
242 65
340 94
229 96
204 34
49 61
349 57
258 99
37 49
367 47
211 60
339 73
205 57
282 35
170 69
316 86
111 70
234 39
105 42
16 24
356 48
147 10
11 57
24 12
218 57
298 4
69 3
219 60
33 65
10 62
78 29
34 91
341 70
400 16
151 87
228 22
47 49
2 98
224 47
142 23
347 71
392 14
159 71
164 18
149 96
236 79
393 8
49 95
106 68
3 16
261 93
209 35
274 90
31 48
203 78
330 86
341 46
372 67
155 88
77 7
201 31
386 16
61 30
212 14
279 47
164 87
238 58
372 86
372 100
86 95
275 28
52 51
352 46
85 28
312 67
384 78
333 39
316 6
360 41
116 95
223 10
132 57
262 34
176 25
158 53
339 92
17 5
149 88
165 69
375 42
32 57
85 37
302 51
123 5
164 45
330 3
288 15
214 94
331 10
104 21
264 73
280 59
111 32
315 50
236 8
315 85
14 73
86 60
85 95
180 72
243 48
356 72
46 73
355 60
156 8
203 24
71 93
28 15
123 59
193 28
185 93
192 12
162 76
20 27
182 8
361 71
367 51
321 84
77 50
183 74
139 56
222 66
237 47
137 51
397 50
312 58
121 66
61 61
269 38
341 99
221 12
291 28
242 48
207 5
302 34
310 62
13 62
326 42
17 37
122 89
274 3
254 12
225 51
39 56
72 53
307 10
49 80
392 3
63 77
6 54
253 4
288 24
157 67
193 19
381 9
287 79
31 47
255 40
372 46
177 55
75 37
48 17
324 50
341 28
86 77
215 29
296 73
228 84
184 5
298 34
330 17
259 87
333 68
37 8
398 7
73 9
143 63
107 48
1 34
338 51
219 94
57 61
400 20
270 63
187 36
373 15
203 100
36 17
220 12
272 71
13 66
52 60
66 98
277 14
112 83
175 51
238 94
39 29
243 4
118 19
72 89
56 92
178 30
137 21
197 18
85 48
163 34
103 47
297 75
310 27
43 35
323 59
18 28
243 3
70 72
28 28
348 76
322 33
177 90
262 49
259 29
382 41
28 37
370 60
253 51
314 72
106 26
15 48
392 2
150 47
99 31
255 26
193 16
292 63
155 16
263 88
226 33
15 41
281 34
205 94
391 20
230 86
206 86
146 29
19 1
193 51
261 35
357 85
191 34
27 22
191 68
16 35
205 78
178 89
374 82
374 52
258 2
196 95
3 88
380 18
82 11
45 23
98 25
162 61
338 67
313 89
174 69
7 60
170 19
41 21
80 68
227 56
303 80
392 57
372 94
257 7
203 2
245 6
199 78
182 69
317 40
14 57
85 66
21 6
58 48
207 61
284 91
23 93
62 32
164 65
350 47
118 7
177 8
146 60
183 28
100 30
244 61
19 72
269 69
144 80
195 41
211 13
5 19
208 81
120 96
234 46
191 59
29 97
129 68
5 68
227 78
299 49
86 74
367 17
307 3
269 80
233 94
248 89
281 87
259 67
35 28
195 31
307 51
121 35
87 64
204 8
339 87
257 64
350 36
359 68
284 41
309 3
11 83
134 34
283 77
82 40
35 8
288 22
305 85
130 94
383 11
200 43
381 63
4 20
237 57
248 89
249 54
121 7
140 2
96 1
284 31
165 85
284 26
55 17
325 47
354 41
264 61
211 84
228 8
26 23
270 54
310 3
73 36
139 42
100 33
7 7
75 52
294 39
325 18
84 47
66 24
204 49
132 49
234 66
281 84
237 14
397 75
311 99
300 49
107 36
63 90
38 50
215 40
224 5
85 89
232 59
113 31
178 58
3 48
197 2
120 31
200 24
152 34
336 15
196 42
130 54
239 94
153 6
339 9
110 51
252 78
133 20
156 36
235 56
377 78
243 49
306 100
13 46
301 18
22 61
389 91
223 9
332 28
235 77
306 42
88 78
228 10
186 63
308 26
374 17
146 16
143 44
327 40
51 92
144 5
359 17
311 12
178 46
130 15
242 30
389 30
27 73
245 99
26 50
112 81
29 60
101 60
50 63
85 1
162 72
301 51
278 62
228 100
329 78
202 84
201 86
314 43
29 20
255 31
285 90
250 82
64 64
282 1
378 45
337 91
124 40
358 92
226 93
73 28
232 100
127 52
227 93
147 95
288 12
191 94
223 57
342 30
383 98
124 39
220 36
273 48
362 83
386 10
120 64
64 87
251 48
32 99
385 56
19 30
110 8
197 98
255 72
247 2
140 16
49 14
91 5
46 66
316 67
135 20
279 14
129 78
245 36
62 55
173 46
106 2
289 95
226 36
348 90
250 9
362 59
255 82
14 76
41 39
277 20
92 17
353 28
318 47
377 46
360 81
250 70
242 91
240 100
16 35
116 40
351 99
382 30
139 96
330 30
294 55
68 89
211 44
17 75
14 69
216 88
173 72
186 20
190 96
92 99
24 49
380 76
51 58
271 71
141 45
246 26
254 5
394 14
117 25
65 77
136 80
358 14
279 31
53 76
347 68
337 81
344 43
28 86
24 64
287 9
196 91
313 94
292 56
245 91
176 9
70 66
144 56
345 9
129 89
44 98
306 31
38 11
185 18
345 97
297 24
328 13

Output for test 8

16441

Input for test 9

2975 10553
268 13
308 76
377 89
148 80
295 61
197 15
143 25
22 70
367 34
179 90
104 57
255 87
270 64
3 54
254 15
209 3
303 34
151 34
214 41
204 60
147 98
344 41
25 94
3 43
271 38
28 26
309 64
252 47
311 58
362 70
289 57
245 51
75 77
268 75
197 65
144 77
169 92
53 51
202 6
198 34
10 27
72 58
370 30
338 87
249 10
185 6
65 28
103 42
124 31
221 94
321 28
205 95
245 48
104 7
142 67
108 9
333 26
56 80
317 40
329 94
146 1
260 71
109 79
124 54
364 22
81 10
311 74
86 88
52 82
381 4
278 87
71 57
175 84
168 99
192 87
244 100
5 81
330 69
250 58
70 71
57 27
255 72
68 57
362 22
65 43
385 22
324 69
240 33
54 25
108 99
182 95
116 93
128 73
164 20
339 49
243 81
93 80
42 86
144 64
149 15
326 34
328 25
258 100
69 4
287 18
175 48
89 62
155 45
131 18
111 39
162 39
377 76
178 6
303 24
49 87
11 35
360 82
185 45
199 10
85 36
203 99
174 19
330 73
251 92
27 89
116 44
322 68
142 37
332 58
52 65
199 90
310 84
54 5
127 11
167 24
158 75
172 17
342 59
270 28
224 26
352 26
210 14
321 7
235 38
89 75
371 5
86 15
9 9
101 39
118 62
317 81
68 86
231 38
98 63
90 43
221 52
357 56
268 78
10 23
267 18
11 44
242 4
87 89
108 8
186 57
86 14
267 55
163 83
331 57
8 1
384 70
255 45
61 34
37 60
231 74
49 79
109 86
98 12
308 66
339 66
343 38
59 4
97 34
320 2
384 85
377 47
97 84
294 76
353 52
40 46
39 79
67 61
168 40
100 12
255 72
97 73
69 45
78 83
45 6
189 79
316 35
254 68
181 89
288 43
160 90
342 10
302 33
161 28
182 77
128 60
340 92
219 82
184 44
77 100
269 98
147 74
334 84
264 6
1 99
353 64
65 24
190 67
294 92
189 36
298 10
98 35
219 44
210 48
65 27
331 23
108 28
338 85
397 36
255 24
262 27
83 74
191 74
327 79
260 91
96 20
67 38
394 79
171 11
310 3
26 87
280 53
215 10
6 20
298 55
370 47
271 54
28 93
137 18
172 87
175 54
371 50
2 72
222 64
93 50
212 20
258 92
316 83
175 61
135 58
146 12
134 66
137 14
300 91
374 37
68 7
73 19
307 15
44 10
89 33
346 61
222 100
134 8
350 38
211 77
371 62
266 91
166 31
98 42
133 22
100 32
7 36
169 60
245 77
337 93
194 73
218 41
263 58
63 25
137 70
367 2
47 84
301 4
311 17
382 51
187 64
146 67
221 33
161 30
24 45
110 98
147 69
236 83
127 35
105 31
386 28
175 63
304 25
122 84
386 72
203 70
194 21
354 92
243 7
313 96
224 22
64 25
202 77
93 73
372 97
344 87
22 86
205 6
301 86
346 71
156 38
88 6
158 27
394 81
241 82
120 89
396 81
76 14
218 88
24 27
63 68
20 57
241 45
101 95
129 67
267 76
324 65
139 73
86 25
257 57
21 65
362 58
103 99
397 59
128 13
205 25
359 50
17 26
310 91
96 10
209 67
185 52
342 75
23 40
81 39
191 35
298 91
335 35
139 31
170 50
145 44
385 86
144 75
111 86
163 33
210 5
198 28
348 30
44 43
99 52
164 18
308 42
40 76
62 94
155 41
249 9
71 54
359 41
309 43
371 7
342 89
133 76
384 74
309 60
97 18
279 60
57 81
36 67
85 45
99 38
78 63
131 65
341 64
263 50
69 97
123 67
333 60
387 81
169 7
76 31
275 54
18 37
297 31
38 76
20 66
310 69
322 32
387 11
178 44
109 5
335 77
270 76
251 43
179 68
264 86
80 85
153 95
38 94
107 70
387 63
140 54
233 82
198 42
11 6
269 94
353 91
327 16
370 60
107 42
126 60
367 67
152 11
17 61
383 79
203 78
393 73
268 99
26 55
317 66
73 59
168 51
87 30
31 13
270 37
47 11
68 48
134 28
97 37
202 88
215 90
353 3
297 45
55 41
199 60
388 10
276 52
212 74
280 72
308 50
101 44
152 95
170 36
62 55
91 97
241 74
331 57
279 8
219 41
141 86
321 54
215 30
222 57
160 60
232 82
36 84
29 68
15 9
292 99
43 12
271 4
45 73
223 44
101 26
156 87
394 63
121 11
84 76
397 81
356 34
281 71
112 80
361 28
288 7
258 93
237 63
146 86
92 1
262 22
134 84
52 4
212 17
361 30
350 10
242 5
3 75
123 21
87 30
217 50
396 96
395 73
25 97
3 41
46 86
22 53
224 23
118 53
305 54
101 72
16 38
357 61
367 13
184 49
55 98
151 2
226 39
164 68
61 94
133 44
390 28
136 57
28 90
5 60
134 14
139 85
111 25
189 96
297 58
207 75
380 61
131 25
381 94
267 63
23 85
54 81
82 12
277 85
48 34
246 65
35 96
39 54
57 26
246 72
263 10
87 24
276 78
287 10
8 54
42 36
255 72
351 31
32 21
285 68
399 59
147 51
202 15
140 41
39 87
211 56
323 89
328 29
226 42
201 85
398 18
335 3
307 30
118 73
196 5
212 84
332 98
343 91
345 10
347 49
364 76
361 47
196 55
340 79
50 76
167 42
149 61
64 18
167 66
210 48
95 54
314 94
297 30
200 74
221 79
308 67
20 80
102 92
72 46
361 51
14 3
205 74
106 40
255 86
395 75
101 40
149 23
365 96
352 22
290 59
26 75
368 58
226 25
203 39
327 4
23 100
391 55
229 55
270 93
169 20
142 39
152 15
37 63
109 50
320 23
114 1
69 19
315 12
382 71
146 77
369 19
139 31
63 74
379 26
77 80
107 18
75 25
288 73
272 100
243 18
286 69
84 100
309 76
95 45
210 27
377 16
1 62
329 25
365 32
110 26
245 10
301 88
390 30
78 68
1 24
137 84
45 50
365 35
362 56
328 74
292 41
69 53
301 40
282 53
384 51
231 25
394 16
86 86
124 26
24 35
19 30
79 76
94 81
372 11
183 69
388 18
5 6
192 78
228 32
42 35
293 50
113 13
235 17
354 100
360 49
266 84
12 57
259 74
364 41
330 89
16 4
279 93
249 45
89 64
344 50
332 92
138 78
247 82
132 22
294 56
329 87
81 3
214 89
284 23
105 14
286 43
211 73
89 28
370 17
159 1
258 84
315 50
264 81
364 60
30 23
212 69
209 11
2 29
85 51
226 31
312 98
382 85
316 70
26 67
282 92
58 10
389 73
178 28
392 58
108 50
155 31
234 1
11 14
337 26
211 70
203 68
97 13
184 21
39 94
42 3
379 51
189 4
255 53
355 74
340 45
74 14
87 7
294 84
373 82
300 33
24 23
292 48
6 79
72 83
276 93
30 93
245 56
318 28
271 35
387 96
182 90
197 57
400 23
2 41
240 77
347 16
339 55
173 24
81 99
83 80
14 67
13 2
363 48
290 42
79 62
400 40
65 60
102 70
272 25
196 67
39 57
324 92
121 89
313 55
72 99
17 33
104 96
113 33
212 7
249 95
393 93
237 54
263 31
12 62
69 34
379 21
159 99
17 58
58 99
74 87
386 87
196 29
100 23
101 87
164 46
173 26
161 68
400 2
76 18
14 48
295 33
233 61
113 65
315 88
365 74
158 11
387 60
284 53
371 65
332 5
174 68
114 64
57 97
244 74
177 81
279 40
318 100
224 7
206 69
380 44
208 51
386 33
240 31
367 46
88 83
261 38
270 51
143 63
79 33
394 34
206 79
46 82
256 34
282 37
292 89
217 41
139 37
207 18
102 8
81 33
71 63
345 4
233 2
209 17
286 71
395 68
203 93
360 90
246 14
368 10
231 80
66 39
164 93
144 49
54 89
10 87
315 79
322 72
272 33
101 26
36 24
197 70
95 99
367 44
76 59
324 31
236 26
392 83
21 22
364 58
183 11
337 58
384 54
78 35
99 14
116 41
356 29
74 28
220 12
168 72
187 18
3 32
121 98
282 67
285 5
193 78
205 15
145 31
74 99
98 4
199 43
243 48
34 32
373 53
301 75
34 94
246 61
287 5
37 55
54 56
89 43
354 57
40 64
393 64
147 62
93 90
287 90
45 42
20 1
96 98
264 31
174 61
294 9
379 41
116 45
277 21
69 55
143 100
321 78
332 42
133 49
14 21
372 64
259 38
358 19
118 24
303 22
62 45
257 46
390 30
391 47
188 38
323 78
135 72
261 20
389 15
211 53
53 31
208 51
290 69
234 1
35 65
385 83
323 33
34 86
194 64
33 18
125 100
2 17
225 29
260 3
107 58
147 55
218 89
145 75
230 24
145 93
42 26
211 66
177 64
347 18
381 99
66 84
171 90
305 5
400 7
249 43
145 5
313 41
96 8
371 35
371 73
387 3
53 85
207 49
241 74
174 4
284 18
187 25
393 72
312 11
45 42
397 38
124 11
172 78
201 82
353 53
31 25
65 2
245 35
177 76
84 89
137 56
88 59
277 16
103 36
221 53
380 50
348 89
152 86
32 18
296 7
273 10
289 84
25 60
36 21
185 93
349 13
73 66
24 47
10 53
316 62
220 68
236 28
8 48
185 60
279 57
112 34
256 88
25 36
299 58
100 20
299 3
25 78
170 15
50 76
354 36
23 52
365 79
154 33
81 11
259 18
262 13
233 7
398 1
270 23
281 29
14 17
163 24
276 81
270 35
210 7
371 50
71 61
93 21
222 65
148 31
177 62
271 78
179 21
186 31
263 57
213 80
132 23
232 62
239 82
351 51
272 15
311 82
42 3
340 70
249 29
85 86
53 50
368 72
262 77
313 53
216 25
199 37
301 90
34 85
164 96
371 72
59 52
399 49
352 64
94 21
63 18
240 59
314 58
297 72
226 60
293 65
185 25
136 72
400 67
95 23
127 37
88 70
257 54
322 62
155 81
357 75
149 56
139 75
155 20
259 61
77 95
62 9
54 99
363 62
120 52
96 58
87 66
245 97
300 65
3 98
44 32
135 77
16 69
354 50
265 91
364 29
87 44
188 98
18 91
38 17
172 89
282 42
312 85
130 2
354 15
285 8
176 87
242 56
99 20
101 98
396 84
146 4
184 81
61 23
185 8
223 45
332 54
312 6
356 32
106 77
365 2
92 30
393 78
330 23
189 65
393 53
398 41
354 42
128 93
292 85
274 7
305 95
112 94
163 3
398 27
107 5
3 32
300 50
156 26
136 66
207 79
137 42
111 66
8 35
263 72
297 89
31 74
322 22
271 52
67 30
334 19
309 40
82 66
96 50
85 81
347 7
296 97
174 73
312 97
135 81
261 32
81 74
147 46
220 38
155 41
101 95
34 85
168 86
69 27
34 20
107 33
94 54
56 30
263 87
123 40
360 78
39 10
20 1
286 10
224 87
269 8
25 57
148 23
33 12
268 5
386 49
15 21
56 10
310 96
14 7
274 41
182 79
266 98
30 75
17 49
133 97
287 47
355 10
76 4
322 55
94 27
192 79
229 22
192 89
400 22
366 64
27 25
311 60
249 57
341 34
63 73
137 70
288 4
92 50
95 18
76 77
223 32
397 45
167 39
286 81
21 64
208 16
355 66
283 59
203 64
60 57
45 86
146 38
230 23
89 68
244 73
278 96
33 96
92 67
28 61
324 20
178 95
348 37
379 22
135 33
107 38
128 53
145 45
248 55
253 91
268 45
161 93
143 70
120 76
46 42
179 30
75 10
290 19
221 13
67 14
362 72
134 100
83 65
71 52
83 66
17 25
80 62
87 68
183 69
100 97
133 78
348 72
109 48
12 43
353 100
183 59
332 38
76 10
400 48
332 41
140 7
75 54
11 12
24 6
233 85
298 56
55 28
27 46
21 11
3 78
360 84
102 44
185 67
340 46
249 71
17 90
371 75
273 43
330 33
46 27
261 37
310 75
362 68
286 50
88 32
217 4
301 14
75 69
390 84
333 50
24 89
90 38
328 37
189 12
89 39
375 71
131 14
257 72
368 80
389 41
135 44
330 54
368 29
161 18
382 88
34 19
90 40
382 25
217 12
199 3
166 71
210 43
155 12
119 70
354 73
223 21
230 16
102 70
326 60
9 98
57 52
137 70
309 9
100 30
278 81
180 33
145 47
319 67
197 9
149 35
278 9
328 29
193 53
272 78
99 28
99 18
356 88
186 41
169 24
41 40
282 81
45 1
57 35
381 87
364 33
172 50
373 69
145 8
131 86
180 29
100 16
246 27
298 29
94 66
105 13
309 11
142 16
312 80
350 21
94 69
254 72
368 12
242 23
259 70
187 31
327 60
306 35
355 88
301 77
35 93
220 90
147 64
261 63
98 61
317 4
235 54
183 68
139 73
248 42
64 37
117 42
67 27
276 65
39 25
363 64
130 75
194 12
73 74
178 89
360 83
362 77
279 9
178 65
49 97
202 13
224 84
79 15
234 55
322 94
91 94
115 88
109 95
198 57
126 92
158 62
155 16
315 48
381 33
144 33
262 70
343 94
148 56
49 6
94 55
15 24
19 29
150 50
356 74
191 78
15 53
280 79
141 31
389 41
306 58
192 48
52 13
12 73
270 87
51 93
38 68
245 83
230 18
14 74
141 8
225 71
180 29
65 78
308 16
183 31
327 5
153 47
198 58
226 69
140 89
217 48
205 65
221 98
281 46
272 27
31 92
336 28
363 66
6 80
143 91
338 67
271 37
47 42
63 29
349 33
118 51
56 55
37 80
19 79
186 72
46 22
288 67
234 99
281 56
36 3
223 58
224 29
135 64
131 7
358 74
244 100
82 4
351 41
167 5
74 60
172 77
218 18
239 56
190 35
209 5
301 13
252 55
283 68
46 48
317 18
182 13
141 29
139 94
274 53
42 100
219 53
308 38
108 2
48 29
113 50
73 26
66 44
117 46
18 82
190 59
355 84
152 34
386 95
343 21
318 39
274 86
64 56
176 75
220 80
248 50
231 56
50 36
130 57
188 9
218 79
90 33
190 8
214 3
88 85
27 91
59 90
330 39
132 83
12 30
58 34
78 56
356 19
71 77
170 68
243 70
37 68
253 74
292 53
332 21
63 28
137 29
125 76
151 68
323 36
299 15
16 92
382 16
354 92
41 33
400 12
31 26
314 43
360 63
151 41
268 2
276 35
374 8
197 41
302 8
343 2
18 89
331 78
111 21
4 62
158 80
154 78
65 18
144 98
228 15
345 42
234 92
371 75
151 38
21 100
60 75
260 5
159 6
116 56
188 61
57 74
345 31
387 81
51 89
82 23
122 37
378 10
241 6
303 57
344 68
50 91
32 52
218 62
287 95
253 60
173 30
290 83
186 7
297 6
344 2
208 44
224 35
88 4
318 16
65 58
68 53
297 25
305 32
291 8
370 9
365 29
301 8
348 65
375 9
267 81
242 32
26 36
264 24
27 54
219 47
301 40
245 34
15 99
329 92
284 25
57 6
53 10
304 84
392 62
270 19
127 36
112 19
11 83
310 83
208 19
16 33
31 27
191 75
392 5
335 28
76 31
26 97
207 81
17 54
132 96
152 93
139 77
347 9
205 14
107 19
224 78
165 70
52 69
204 23
73 93
86 8
315 82
377 27
182 34
369 52
68 99
396 89
97 52
156 35
53 76
384 70
142 21
68 39
254 59
364 23
93 42
355 5
49 31
293 27
251 78
154 66
311 27
148 88
353 39
390 96
89 94
313 24
355 81
109 25
212 44
139 45
40 82
142 35
314 97
349 94
324 7
383 78
12 82
110 45
161 10
196 84
64 61
128 69
220 47
172 97
90 86
199 83
34 14
222 74
255 95
91 45
337 83
25 97
378 22
34 35
339 30
108 100
119 22
300 62
52 29
48 96
30 18
238 57
323 97
28 91
399 72
259 94
113 89
124 11
292 81
321 34
55 32
167 11
9 80
273 34
300 8
319 73
238 47
201 85
304 23
60 50
77 11
281 13
94 92
103 28
315 66
333 87
330 17
78 12
164 97
154 6
85 33
331 44
369 58
326 60
365 59
33 29
381 37
14 4
344 76
50 53
100 76
4 18
68 34
398 21
1 26
362 48
111 97
242 93
6 62
187 1
343 81
156 14
77 84
353 62
14 89
387 33
185 92
168 21
394 97
152 74
79 26
237 40
151 69
159 85
30 39
145 4
5 69
147 8
252 74
83 53
290 60
321 47
396 93
190 95
325 66
291 63
302 16
204 91
92 7
155 33
289 35
213 68
148 5
173 7
322 57
10 69
205 26
76 70
231 40
306 63
356 68
378 70
364 11
99 43
364 12
170 80
165 52
122 25
123 22
328 100
366 54
127 15
318 30
312 73
254 82
72 34
161 89
304 40
239 93
245 41
329 83
395 25
232 84
399 39
373 54
48 38
23 68
56 59
68 32
127 1
271 39
315 45
227 3
41 53
121 66
293 94
44 99
336 65
8 51
249 11
198 48
48 14
121 3
138 22
199 88
233 83
109 6
1 50
395 70
27 39
5 46
19 91
397 1
367 93
8 86
50 56
132 74
202 25
63 34
183 32
50 42
331 29
391 21
204 88
332 67
384 83
315 42
280 13
206 16
356 96
286 10
250 85
353 82
351 43
346 1
78 8
325 90
47 50
300 68
184 96
114 2
367 85
174 59
320 98
98 64
386 18
81 61
80 52
99 81
244 59
36 50
54 18
318 54
76 68
146 44
178 6
336 48
245 100
328 99
46 11
149 13
147 21
346 16
262 18
315 48
12 46
181 93
10 67
224 22
85 50
119 50
287 79
343 57
223 31
103 86
254 53
301 25
19 15
184 67
339 72
113 63
175 91
175 21
93 52
314 10
17 32
249 58
86 34
372 15
182 16
221 85
213 81
148 39
35 79
173 83
3 67
60 79
185 44
61 33
339 49
375 85
165 66
152 90
329 3
227 52
70 57
46 48
8 74
284 45
126 51
386 31
234 23
78 9
94 43
187 18
370 75
29 5
241 55
374 84
168 87
264 7
306 40
290 50
244 1
239 5
251 20
111 89
49 35
170 58
363 49
399 53
147 72
119 23
12 16
331 70
81 40
104 48
37 7
155 57
104 35
368 59
207 75
261 1
253 50
165 61
1 53
186 56
385 67
161 14
137 28
245 24
303 42
60 38
209 15
325 81
363 74
316 75
123 59
285 42
6 58
281 80
34 11
369 53
26 63
76 59
171 7
74 43
169 19
287 72
88 44
397 67
366 5
259 85
239 82
165 19
390 35
313 93
107 32
130 1
160 95
382 52
362 68
37 92
162 38
254 37
197 94
168 65
360 78
310 72
166 41
120 71
386 17
36 48
29 100
393 21
220 22
261 69
228 14
134 75
70 48
334 64
301 34
155 42
180 22
291 39
224 94
198 23
267 19
234 13
34 55
147 96
219 89
100 54
111 10
67 73
252 10
115 99
216 33
372 71
105 60
87 23
276 44
363 33
180 78
141 84
387 100
317 72
58 13
294 72
325 86
145 14
210 55
32 51
51 51
340 60
54 88
359 96
228 76
82 81
160 55
313 94
121 74
174 21
79 50
127 79
80 23
195 6
269 45
115 77
87 8
157 65
159 36
235 15
25 2
3 62
129 49
310 73
302 42
100 17
289 79
119 53
383 72
263 92
165 56
68 39
85 10
398 35
79 94
165 55
123 66
329 30
122 77
209 22
31 58
88 67
32 72
42 47
337 50
113 90
344 62
53 90
230 62
271 45
85 29
152 88
249 48
91 26
103 67
124 26
181 47
196 56
322 80
15 4
211 75
119 37
159 49
10 41
307 26
217 63
92 60
350 48
234 36
311 66
6 7
359 82
257 53
339 47
236 100
55 89
292 76
150 21
392 17
85 55
102 75
347 100
59 27
235 44
343 92
64 19
171 16
375 74
201 9
34 94
360 62
313 92
130 36
258 24
263 29
384 18
54 91
137 98
338 12
142 57
77 82
32 35
391 71
379 54
123 74
284 19
299 100
170 34
357 20
156 45
363 34
248 46
319 57
359 98
184 65
175 85
57 14
159 73
174 55
128 79
162 91
207 85
37 40
9 56
90 32
89 42
91 38
47 56
82 88
260 50
228 75
289 72
2 27
396 66
2 55
365 45
290 15
219 46
164 68
254 11
121 51
108 45
189 60
91 83
92 68
185 98
297 39
138 80
180 92
343 100
204 87
262 80
240 55
350 95
353 21
280 25
84 6
330 94
203 24
68 61
238 18
252 10
3 93
100 58
141 64
384 21
37 74
296 41
167 90
315 74
298 56
195 81
213 27
400 48
234 45
397 39
352 65
61 84
283 31
62 44
141 46
124 55
373 42
332 56
247 7
325 99
112 40
94 59
271 25
350 13
4 43
104 78
46 58
59 95
96 80
186 62
242 8
316 69
191 77
338 85
207 97
48 38
378 22
174 97
273 65
242 53
239 52
214 72
185 68
341 24
85 76
240 59
97 11
81 26
287 92
313 16
182 81
306 99
60 23
331 21
387 56
21 9
139 69
74 45
187 44
308 24
190 87
99 34
19 88
29 92
379 65
41 82
318 1
133 88
74 8
221 81
217 34
153 99
377 81
381 87
160 56
155 64
219 41
16 7
329 36
275 44
225 81
58 17
89 31
159 60
314 80
393 69
70 69
60 39
192 43
342 58
74 81
20 17
382 99
69 79
390 56
345 10
156 45
45 25
367 54
158 48
339 47
289 33
5 64
156 36
397 30
352 23
158 88
167 29
379 35
170 35
328 7
380 28
5 97
44 1
9 64
127 84
310 19
120 77
69 69
72 3
90 38
388 71
339 68
18 18
45 58
48 32
23 17
240 31
250 4
282 50
385 31
319 94
395 82
8 60
309 95
78 44
77 70
328 56
104 47
232 66
154 42
206 39
396 94
294 46
365 50
230 67
37 88
14 97
26 88
203 76
371 46
301 65
398 54
387 19
207 61
30 41
385 5
44 56
374 98
117 29
176 5
273 13
70 91
47 60
16 29
160 35
81 41
341 57
167 58
279 39
395 8
359 3
237 83
149 82
134 22
68 4
31 88
205 54
78 87
66 71
131 34
300 25
10 59
275 97
315 34
88 63
180 55
306 48
309 58
165 70
35 24
377 46
366 14
338 93
396 68
349 66
321 43
234 77
219 79
63 26
243 60
274 60
32 34
162 34
135 93
26 26
233 72
319 61
95 33
241 63
99 24
356 64
211 100
52 5
191 36
348 49
181 9
187 62
16 87
118 44
379 2
358 97
373 37
87 18
391 50
90 21
115 84
235 71
251 30
97 57
139 71
48 2
255 12
109 25
50 97
23 32
383 36
259 99
371 3
358 70
88 43
46 95
89 64
267 85
313 36
193 35
304 4
148 48
66 63
209 72
8 72
373 3
80 11
243 40
73 25
154 28
84 56
244 35
363 87
56 60
363 70
155 30
34 99
284 41
172 99
229 68
245 18
351 82
55 37
156 79
1 97
5 36
152 98
14 17
107 28
73 90
176 38
167 20
43 46
323 14
78 31
79 66
365 57
318 13
375 99
262 82
181 82
195 81
364 3
112 53
165 15
132 41
315 69
21 90
52 37
340 38
137 58
361 89
10 42
137 46
371 39
99 11
49 36
314 13
115 13
178 51
45 67
226 99
170 17
243 15
21 73
387 7
356 13
205 82
293 9
352 55
374 85
108 12
48 1
303 6
162 10
10 82
39 84
292 79
49 38
74 56
355 40
261 87
310 11
236 6
57 31
11 46
16 87
230 40
301 97
390 14
266 74
62 95
276 65
336 36
332 86
130 25
94 36
264 98
369 19
50 94
372 13
131 95
87 94
73 73
171 74
125 82
244 95
159 43
104 98
298 48
279 95
329 70
92 60
362 60
21 23
19 48
257 80
208 76
145 40
49 75
99 72
311 48
227 100
234 58
14 61
257 97
301 75
89 18
171 50
335 64
318 35
11 10
242 12
377 15
91 75
83 39
333 34
29 92
330 49
86 26
284 96
389 16
280 93
197 38
63 89
326 19
216 77
34 59
360 69
216 39
296 99
94 79
332 25
153 89
326 31
355 27
167 3
66 45
157 72
148 71
335 50
384 11
232 18
198 92
374 62
388 54
90 48
39 12
253 14
373 98
327 37
125 65
209 5
305 43
171 70
353 77
290 24
399 47
7 83
194 32
32 24
142 7
3 72
136 79
329 54
301 63
276 36
135 60
293 24
152 21
155 86
219 41
261 69
242 12
370 15
106 8
360 12
44 86
374 77
254 54
320 29
79 44
45 20
222 44
27 37
25 16
100 31
298 5
81 59
285 4
121 9
324 74
183 17
166 5
105 52
268 4
53 96
280 61
341 56
379 2
54 41
192 94
162 40
308 56
334 43
134 86
115 3
396 97
86 11
314 18
184 63
396 29
43 92
103 78
223 7
34 27
103 96
200 100
338 46
24 39
200 3
143 15
50 35
190 83
397 87
102 26
159 30
93 49
393 46
69 81
217 60
147 22
370 81
243 24
394 85
36 33
65 38
327 90
176 59
373 72
215 46
270 13
172 69
126 82
186 44
205 10
54 24
333 6
28 21
284 22
255 78
181 35
334 21
79 73
97 33
25 65
60 78
253 67
351 26
13 60
352 7
326 88
2 34
400 79
278 35
316 53
249 37
245 26
209 6
69 35
90 53
358 37
365 90
188 39
160 63
236 40
219 18
217 87
10 21
107 83
124 47
369 71
213 40
336 37
261 98
148 72
327 74
360 63
394 17
372 84
306 48
221 50
348 61
304 7
69 94
151 20
285 28
66 26
50 45
321 93
182 65
242 41
212 67
167 38
195 93
361 41
205 89
291 35
253 20
220 91
363 89
162 74
243 94
319 31
352 66
144 62
316 32
45 71
14 61
344 16
186 1
319 87
2 77
189 34
399 70
275 37
244 22
324 85
220 28
173 31
74 81
2 86
381 99
104 98
222 34
92 33
176 82
6 41
157 68
367 55
288 43
10 68
207 15
22 32
283 79
199 36
273 17
206 7
361 52
102 68
393 78
177 51
14 22
18 41
378 77
255 91
22 92
52 86
275 27
99 56
394 64
224 66
95 54
96 76
198 92
135 66
120 11
373 90
77 98
270 62
123 13
90 20
353 4
268 83
190 52
137 6
382 56
14 48
29 10
239 75
50 59
384 15
304 76
33 82
184 8
320 13
48 23
119 55
217 36
6 41
11 31
166 19
53 81
297 33
214 49
93 94
142 77
183 97
128 71
375 7
346 51
144 76
227 78
176 79
347 96
236 89
128 22
178 18
31 82
337 63
5 65
138 40
398 90

Output for test 9

23513

Input for test 10

3402 12880
70 37
267 89
278 48
76 76
259 51
344 86
313 48
308 10
353 91
162 71
321 10
261 52
179 75
86 91
323 19
220 91
89 84
337 61
147 16
362 31
147 58
99 38
97 9
191 63
156 1
99 19
84 68
22 10
164 87
189 47
119 77
293 53
286 57
97 89
291 26
34 22
55 52
45 89
369 68
228 34
252 6
309 50
333 6
260 46
259 43
269 47
247 61
187 92
226 38
378 62
202 99
144 54
185 84
75 37
90 16
79 48
2 85
93 84
386 69
95 77
33 36
116 70
117 11
87 30
26 66
293 60
282 49
182 17
111 38
158 80
360 63
15 27
129 57
170 25
346 30
222 33
171 38
244 59
10 86
179 71
323 50
268 64
278 19
289 60
178 48
61 72
335 30
300 27
118 40
147 22
34 12
329 70
33 20
174 40
209 98
159 85
159 71
197 77
164 4
121 53
272 23
29 18
208 44
271 84
22 8
3 78
64 32
53 95
269 87
179 5
101 83
135 18
166 25
108 42
50 25
157 84
139 12
252 61
294 90
115 98
86 28
199 66
38 10
85 49
297 91
305 16
271 46
323 73
65 50
360 72
125 90
50 43
262 75
88 6
376 69
336 26
367 94
204 7
82 2
26 99
38 77
57 65
175 42
141 14
267 94
352 70
28 8
228 37
301 9
64 45
354 14
323 7
167 38
42 34
312 97
374 91
100 91
160 65
393 44
97 39
186 67
359 72
262 86
132 90
89 66
43 6
360 13
208 96
276 39
261 26
35 41
71 12
234 25
186 89
73 29
274 81
258 32
285 67
229 82
110 82
181 24
168 13
170 85
226 45
219 11
121 35
78 19
187 12
237 32
257 44
146 61
5 75
269 92
333 55
308 43
345 68
166 62
365 72
85 69
164 71
311 88
204 74
58 68
351 38
319 65
212 92
138 92
150 51
191 100
202 68
160 93
242 33
136 82
232 54
307 61
307 81
323 88
39 100
374 47
129 25
319 97
51 4
352 58
166 1
122 68
201 37
266 10
44 34
312 30
280 17
192 67
81 96
154 74
156 60
340 40
348 95
395 61
240 69
36 92
168 60
340 11
83 22
100 51
109 74
228 74
362 25
384 8
193 10
309 88
353 33
252 13
157 21
152 68
96 24
146 33
193 73
57 81
198 81
334 71
19 64
72 72
258 98
36 27
58 58
387 98
387 27
377 5
47 98
45 50
40 47
69 54
54 69
293 30
371 13
76 85
146 15
387 2
239 60
113 63
332 28
176 1
84 86
290 77
206 73
27 79
312 66
150 82
390 19
242 73
294 30
140 21
252 17
325 82
201 29
175 24
334 67
359 48
268 41
329 82
19 84
65 8
368 43
192 45
311 10
158 83
47 7
148 27
147 58
266 50
361 90
47 18
161 37
221 19
313 69
194 12
125 64
306 92
343 56
138 98
244 93
147 70
126 66
69 58
177 16
192 33
135 20
165 94
110 72
167 30
116 9
74 54
2 48
303 33
379 67
339 85
163 56
259 7
9 28
385 20
174 100
11 79
178 93
17 32
377 71
55 81
285 74
105 20
113 44
306 99
31 90
2 81
224 62
98 36
224 100
294 1
236 62
53 81
198 37
51 51
70 3
323 34
353 22
365 99
387 13
395 69
339 37
29 66
396 17
132 15
150 46
145 48
364 55
314 52
338 71
79 63
106 47
135 47
10 28
399 70
49 8
89 54
372 68
22 82
76 8
119 56
135 74
306 38
339 70
256 4
330 93
358 39
203 34
331 18
354 14
82 41
199 24
199 41
41 22
92 15
312 60
30 91
132 10
260 93
40 5
178 75
220 50
354 30
176 39
184 1
167 73
1 58
126 4
345 18
185 47
32 70
15 68
88 40
255 100
144 92
20 29
328 56
61 58
189 99
120 68
164 23
202 59
390 25
381 62
333 19
121 13
85 67
369 54
115 5
263 86
110 20
114 69
382 71
378 4
172 99
90 87
113 74
103 68
380 1
383 58
382 44
75 25
288 24
29 88
379 56
152 18
126 20
299 90
284 54
2 97
212 73
278 57
229 4
136 83
193 15
379 88
15 10
270 16
205 72
127 40
161 58
77 34
7 82
400 5
234 79
277 4
113 94
289 14
250 89
339 17
61 46
342 32
208 73
97 45
36 48
64 3
216 81
193 80
279 29
37 73
43 86
233 32
154 24
100 40
252 99
105 8
87 26
23 11
192 74
349 70
114 23
297 29
154 51
210 2
74 51
221 32
40 68
135 97
151 27
130 87
57 42
367 23
29 11
337 4
319 66
324 28
180 11
329 52
120 86
75 64
266 22
395 10
138 42
396 34
397 83
193 2
242 11
222 13
21 70
309 78
380 61
6 92
248 9
84 20
186 75
373 51
24 77
316 80
61 89
64 2
296 65
355 88
161 98
156 68
31 45
149 71
387 55
306 30
46 18
87 6
55 40
246 100
219 67
191 96
124 77
280 27
66 22
275 71
372 20
111 31
244 31
287 93
4 78
385 46
43 97
232 44
59 35
234 100
242 70
48 62
376 47
103 38
137 13
58 14
73 13
152 12
184 21
140 80
45 19
237 21
257 98
150 27
82 40
237 37
71 92
162 86
294 92
111 36
24 54
388 25
148 24
366 58
366 72
38 61
226 78
347 35
248 33
172 40
179 85
394 98
163 8
316 74
43 91
364 71
84 20
162 12
14 87
180 24
280 45
84 83
174 90
221 93
92 21
280 51
306 66
286 23
181 6
118 98
286 41
146 41
362 52
224 38
85 95
96 99
111 54
164 49
291 77
380 22
141 72
67 43
159 1
260 21
354 66
157 15
360 41
69 95
311 21
185 21
36 40
47 35
390 97
102 14
286 75
34 90
160 43
278 96
122 65
268 19
68 41
203 53
199 71
357 69
398 1
144 36
280 69
179 31
173 93
163 87
354 89
215 74
52 34
157 10
316 75
29 95
293 76
259 43
227 32
289 23
198 94
309 56
50 3
243 16
367 96
96 99
17 14
189 66
364 65
383 93
367 52
317 28
39 24
251 34
199 73
223 5
361 67
299 95
289 60
217 94
370 28
122 78
24 97
138 27
375 79
205 66
69 30
357 41
248 7
169 39
6 84
383 21
274 43
358 3
348 52
343 82
258 82
78 81
306 55
303 67
370 32
169 49
367 44
357 58
120 69
47 73
234 71
220 31
390 96
250 48
295 90
385 9
298 33
91 43
194 39
11 86
290 14
243 67
39 65
143 50
62 75
397 14
284 1
140 52
259 12
62 53
225 52
309 17
400 36
209 78
286 55
358 34
174 46
337 25
289 13
129 5
286 1
81 62
246 29
208 87
24 40
290 28
385 60
183 14
91 30
372 91
183 24
377 38
177 20
218 6
249 21
400 77
26 72
230 25
335 91
16 55
10 19
231 49
305 31
294 32
33 16
129 58
270 9
66 38
371 8
216 45
385 70
115 64
393 95
11 90
79 84
324 59
194 97
63 32
328 27
90 36
69 52
301 5
168 72
85 99
135 10
136 22
19 77
236 65
264 27
35 31
276 10
274 43
157 16
24 61
164 81
140 39
399 20
389 52
35 4
334 32
121 84
152 30
345 65
168 63
202 50
17 2
293 6
369 93
118 93
86 7
239 25
113 74
98 10
328 66
124 80
394 84
203 3
309 57
368 67
131 90
210 82
72 61
136 37
225 28
52 74
321 95
55 85
182 58
353 74
386 75
9 93
32 39
16 98
10 55
342 24
238 20
317 82
265 85
273 81
96 31
291 74
169 70
162 94
42 23
245 98
205 90
56 9
395 95
269 31
104 17
114 21
110 36
193 5
198 15
213 67
364 73
207 93
393 10
330 59
152 42
61 45
396 87
161 1
51 50
249 47
166 33
185 1
396 31
8 44
56 84
44 18
4 74
378 28
337 39
139 48
199 10
332 18
68 99
339 3
122 49
99 65
380 72
69 35
24 88
311 20
78 86
333 35
214 64
39 40
274 79
166 34
177 31
12 84
109 69
181 48
272 63
84 43
203 23
166 59
167 79
348 69
293 29
177 88
223 70
9 38
250 7
387 57
292 58
388 31
16 11
153 25
169 14
243 76
42 75
140 65
327 56
214 64
290 12
18 58
261 13
113 6
27 58
385 49
284 32
119 82
58 31
171 8
227 34
217 79
109 59
6 74
351 64
236 43
36 4
207 75
306 26
70 49
320 22
367 63
368 82
10 34
200 59
19 24
202 80
262 3
285 11
127 43
149 25
186 69
338 44
341 11
397 82
82 90
324 92
383 80
1 20
124 65
356 38
232 79
269 63
48 23
370 14
310 69
153 69
132 96
357 31
338 68
319 46
92 71
141 7
363 14
262 100
215 58
203 30
36 25
371 54
239 69
135 59
223 21
277 22
320 69
356 49
291 21
58 33
333 15
305 41
350 89
58 68
105 1
326 69
145 91
30 95
251 31
166 78
109 68
11 40
286 25
305 78
58 62
27 94
152 96
198 96
352 26
348 77
192 96
123 38
216 45
34 80
1 100
101 98
13 39
230 13
205 33
119 33
32 88
62 3
126 59
359 32
394 94
190 99
282 46
238 93
363 30
191 55
235 90
69 70
114 75
120 98
267 34
157 98
50 97
187 79
56 52
97 2
181 71
398 89
165 54
158 10
123 28
159 79
35 86
317 18
370 17
235 31
298 20
149 87
269 30
152 4
240 15
189 33
169 72
238 63
118 100
339 77
293 93
340 4
117 85
37 66
63 82
261 70
194 10
382 91
201 15
336 74
239 70
81 1
239 88
126 15
341 26
289 8
207 17
248 21
104 56
387 73
259 76
108 16
210 66
124 63
101 58
231 49
113 77
183 57
191 84
155 46
327 1
388 12
286 65
145 20
386 90
309 61
169 99
126 54
65 11
295 85
115 42
280 44
353 86
253 49
231 20
243 49
366 95
60 69
39 39
149 19
366 82
135 46
29 79
227 90
286 84
187 71
190 68
105 2
285 53
88 90
72 22
100 89
178 34
87 71
121 18
211 4
76 86
2 52
270 7
147 98
388 92
19 54
128 1
85 18
363 61
295 23
50 77
11 46
83 60
66 72
253 21
366 43
192 11
47 46
17 97
210 57
81 4
353 5
19 65
122 50
142 96
176 39
34 83
248 50
101 73
17 90
393 45
247 9
224 98
208 41
277 43
23 12
113 43
139 47
11 40
164 71
136 32
89 81
355 19
92 85
387 85
332 32
175 31
79 71
285 18
216 29
47 7
91 18
144 22
18 88
54 7
309 10
157 67
120 11
139 71
287 77
393 43
271 68
397 4
132 3
250 67
385 76
324 2
146 3
257 65
263 55
189 96
270 38
337 79
39 55
43 74
301 59
176 76
1 17
367 41
57 55
93 81
191 46
225 5
1 23
295 89
368 48
5 80
16 44
234 19
360 14
10 19
222 13
20 6
384 99
115 6
278 44
12 39
57 99
215 68
327 33
39 61
81 93
248 75
181 51
219 30
289 60
220 69
258 92
210 82
310 87
54 20
71 10
131 92
121 6
241 54
340 44
9 14
85 17
388 87
49 21
149 7
375 85
257 40
76 24
324 79
170 29
305 5
95 87
385 81
210 39
175 72
224 4
308 54
120 14
348 62
95 4
318 77
48 42
280 95
141 81
266 20
81 68
271 47
9 41
395 79
1 80
366 47
57 66
91 100
356 50
186 79
115 81
94 25
257 40
400 99
93 51
28 68
252 33
283 38
152 21
318 22
384 11
97 71
271 69
272 36
205 42
335 55
312 39
42 31
206 31
73 92
334 59
389 29
99 35
290 48
292 82
83 65
216 15
153 4
226 15
61 94
383 81
207 92
359 43
119 65
377 50
91 16
239 92
342 35
298 21
215 67
49 18
10 24
271 57
92 52
302 63
332 36
16 35
148 25
231 55
166 86
57 41
185 63
385 85
254 39
397 39
163 69
386 64
211 45
189 83
32 88
120 4
30 79
189 90
153 25
206 27
73 1
357 45
39 84
204 100
165 83
154 67
296 62
373 17
174 66
212 96
337 64
277 67
206 14
145 71
339 96
236 53
228 25
122 75
307 9
54 65
212 80
40 44
154 56
218 14
330 91
327 49
215 50
197 1
285 71
327 4
175 30
95 2
51 3
144 40
237 28
306 15
193 73
273 65
43 5
370 35
204 67
190 14
225 75
313 87
366 78
59 58
274 56
85 93
13 37
265 70
110 91
64 87
55 3
206 92
276 79
91 67
145 77
63 70
89 94
365 29
162 60
88 22
135 41
124 66
131 68
376 85
279 68
89 16
324 58
254 8
77 10
103 90
44 25
128 67
12 51
10 70
361 36
152 71
51 92
199 84
353 67
316 61
221 19
156 89
263 31
171 1
332 64
297 16
30 41
8 11
115 73
367 90
232 60
210 61
170 11
387 41
221 82
56 44
192 29
227 99
362 52
271 92
12 85
320 63
155 83
282 17
167 60
273 32
54 57
306 14
111 46
254 95
18 90
392 65
94 59
41 53
164 38
193 80
43 66
31 76
50 56
189 93
233 5
257 6
181 97
85 32
150 92
214 3
399 8
321 94
151 56
129 82
22 12
210 47
40 1
20 79
382 22
139 87
22 6
45 22
146 73
150 2
147 99
269 94
305 8
119 1
386 76
48 12
187 45
91 70
93 51
8 82
274 38
2 63
353 18
174 99
386 12
268 34
44 24
310 29
156 91
313 55
312 71
35 29
234 57
98 93
217 99
111 12
123 76
213 46
118 84
333 6
11 92
218 77
116 83
195 9
134 68
349 27
229 90
281 1
216 51
335 11
57 17
376 5
394 75
252 89
160 16
222 79
397 94
286 83
377 61
195 71
141 96
351 37
328 41
23 8
152 2
239 15
251 18
383 16
197 74
339 17
256 55
331 72
22 50
6 42
150 11
6 19
42 19
183 2
205 67
266 16
49 80
20 39
46 29
328 96
246 78
103 82
208 74
44 74
320 38
144 59
391 15
141 59
399 71
399 23
178 84
309 66
256 26
245 74
186 44
165 82
7 6
69 8
45 61
52 71
384 72
130 19
169 37
284 62
272 77
92 80
219 31
307 7
350 60
160 95
37 91
223 56
20 66
120 39
324 54
101 72
291 29
335 77
311 28
17 26
318 25
239 65
287 86
46 35
356 53
173 33
390 90
295 19
13 18
369 73
351 48
250 73
63 76
187 42
392 38
117 76
165 26
339 19
274 94
137 92
102 20
263 76
109 26
193 31
188 63
217 14
100 51
250 94
62 42
346 89
101 67
223 56
269 47
143 13
155 56
233 57
100 76
153 12
42 99
380 63
298 22
214 92
46 25
51 50
217 83
309 60
346 27
278 61
57 40
294 25
145 29
67 2
168 21
216 96
386 2
62 26
310 32
104 15
300 59
19 93
280 85
71 2
330 48
332 60
150 34
40 67
273 97
309 40
378 86
128 67
115 70
163 4
35 43
82 81
58 42
279 89
123 70
25 80
379 84
124 63
69 30
262 10
351 46
243 40
142 2
271 82
264 61
159 56
361 27
229 23
352 62
182 72
261 45
113 36
329 77
229 75
26 55
387 52
157 7
63 34
26 38
79 100
67 8
188 44
253 84
353 21
315 99
82 24
10 36
16 24
72 12
179 94
198 20
198 87
29 11
394 80
104 58
325 90
157 93
232 9
144 72
25 38
349 56
42 36
279 78
197 87
57 28
151 94
77 37
343 22
60 4
29 35
233 43
364 82
224 7
162 80
308 17
203 23
1 75
58 97
391 94
378 14
350 26
26 62
113 41
133 84
109 80
86 74
76 41
106 45
126 21
64 40
10 64
258 48
350 92
1 60
341 14
76 33
56 33
23 9
233 72
39 85
8 72
390 16
244 77
151 11
265 49
222 9
48 99
197 4
299 83
284 40
286 96
173 89
92 59
296 38
245 56
288 77
190 61
271 100
380 87
254 14
216 18
187 95
71 6
272 28
177 41
243 87
267 87
139 55
320 8
105 91
324 53
146 55
114 40
382 74
368 22
348 92
214 31
299 59
81 14
192 98
43 50
44 89
360 74
294 33
43 93
358 44
181 4
101 61
307 1
143 24
85 64
303 92
99 44
295 49
322 57
130 55
111 88
308 52
271 93
121 84
51 95
123 89
317 38
346 29
207 76
196 16
278 26
238 41
321 21
378 46
145 40
123 90
266 24
53 13
149 11
20 44
27 24
107 60
355 81
144 36
14 97
89 91
372 51
370 22
1 16
160 79
60 13
67 59
98 51
366 26
43 75
310 77
319 36
113 52
262 30
306 89
354 16
175 56
222 97
214 15
251 30
71 56
371 42
107 71
46 6
384 78
188 35
74 12
256 40
256 71
243 27
146 21
348 36
337 40
382 34
130 40
146 92
245 56
194 7
29 90
241 26
201 88
325 26
54 14
31 68
161 86
332 91
347 26
286 11
124 44
324 10
208 68
368 18
273 48
255 83
236 22
62 1
97 28
248 38
182 39
341 34
323 19
253 58
311 94
312 53
114 48
373 39
307 36
288 91
22 63
72 46
126 13
201 50
283 26
194 26
370 24
383 47
241 21
170 76
213 95
119 2
302 23
391 52
230 27
324 22
133 90
123 73
69 25
234 2
167 97
58 23
332 66
7 32
321 99
119 9
342 57
243 17
94 93
178 77
252 54
147 31
381 40
391 58
370 31
297 98
145 54
42 92
256 29
229 88
152 19
324 93
343 91
377 19
134 5
218 79
193 4
145 8
113 14
298 28
234 90
278 96
106 43
141 71
129 41
301 59
148 67
194 7
157 22
86 51
149 45
153 23
29 100
349 93
148 53
218 73
125 29
306 1
61 62
256 67
293 21
337 43
364 91
199 88
44 50
123 4
208 71
391 8
256 16
215 44
357 94
372 69
118 17
355 92
294 6
342 39
258 100
103 17
277 81
40 69
316 29
171 56
6 82
242 15
196 96
260 12
300 90
109 28
52 44
355 85
25 88
394 25
356 61
153 93
149 53
90 57
156 75
373 64
374 6
396 30
49 47
164 9
352 56
168 32
69 81
213 79
5 94
57 73
39 83
339 95
145 60
325 28
136 83
85 85
394 32
323 81
89 34
321 91
277 73
123 96
156 61
331 45
23 12
74 1
224 100
262 70
230 1
133 77
229 88
26 42
352 47
19 48
10 28
255 17
294 9
11 13
83 32
45 4
336 92
165 62
284 65
293 6
239 73
11 74
316 19
46 21
297 34
268 90
208 80
87 42
398 9
342 37
329 32
167 35
16 83
344 49
284 29
148 3
311 7
141 73
190 8
288 17
31 62
55 40
19 37
69 71
155 99
294 34
209 37
231 81
28 97
257 99
260 21
17 40
293 53
50 35
54 90
375 96
309 37
97 26
295 84
363 53
375 56
287 81
197 26
252 85
12 59
369 28
345 52
58 92
323 48
352 98
115 51
391 28
271 54
314 49
129 32
92 38
42 94
346 34
238 31
391 18
200 76
366 81
342 10
42 53
371 32
375 66
271 81
275 21
82 7
232 92
322 25
237 71
327 17
38 32
266 93
324 45
244 88
208 3
140 85
160 100
161 52
268 44
98 59
224 26
204 91
120 93
200 4
201 52
264 86
201 85
303 4
129 75
371 51
397 26
374 86
388 71
57 6
192 81
128 51
299 52
280 74
255 34
370 79
221 26
297 58
248 91
367 63
69 55
250 95
95 82
338 81
207 78
324 79
397 78
224 47
248 45
239 56
123 7
31 61
250 46
299 27
63 35
370 8
290 44
189 10
60 20
128 35
82 30
150 22
374 92
51 94
126 77
230 95
158 92
217 8
284 64
262 52
266 19
205 68
222 35
45 13
221 69
51 73
98 6
253 17
100 4
239 85
329 2
361 26
201 6
397 27
357 96
255 81
276 75
239 89
298 54
58 41
93 85
260 35
359 26
45 89
353 88
49 31
36 24
75 44
105 74
215 82
390 13
252 52
347 9
397 82
164 6
203 24
209 51
44 57
136 71
373 6
327 44
121 97
255 24
134 78
263 69
178 74
92 7
35 8
189 26
37 44
15 2
265 88
400 71
167 44
382 7
29 18
312 30
134 20
83 3
227 30
279 63
281 17
333 79
161 78
376 91
27 98
22 29
31 33
299 1
40 79
196 58
231 92
68 54
347 87
364 92
3 12
359 59
394 81
159 10
203 71
328 62
13 8
83 7
205 42
278 81
351 8
251 77
70 82
279 74
44 100
168 65
115 36
46 35
173 44
75 51
63 40
285 65
284 18
66 79
245 66
225 11
131 70
178 73
335 99
88 52
270 94
264 22
295 10
81 56
338 5
185 91
148 62
258 45
34 58
376 94
112 43
344 14
71 100
110 31
301 8
117 19
264 51
214 87
240 86
1 14
278 3
182 50
226 81
166 51
213 76
212 31
151 88
197 52
284 84
177 89
93 31
371 86
186 63
61 59
325 11
68 24
211 96
207 45
347 68
153 99
383 45
148 98
81 20
171 31
305 79
166 12
16 82
20 79
343 86
40 87
328 33
130 51
90 56
358 87
30 47
92 70
159 84
14 85
117 57
382 52
350 81
336 18
257 95
68 13
305 52
81 3
390 13
16 97
251 17
258 49
330 42
66 93
253 59
282 93
399 50
12 53
6 76
392 100
357 95
303 85
119 65
133 62
378 80
63 16
2 35
84 60
172 79
37 48
110 100
370 5
154 89
79 4
175 19
14 6
255 54
332 14
220 57
290 59
281 5
377 92
369 7
52 72
348 16
93 64
341 1
40 47
370 39
235 82
61 6
346 13
301 100
96 99
236 32
124 45
218 15
226 35
378 4
155 61
192 32
286 41
147 26
117 86
192 58
205 3
203 79
243 54
37 100
67 23
83 62
227 12
275 18
167 51
284 55
370 93
329 32
242 55
346 2
307 8
42 35
51 41
151 6
277 47
353 2
135 71
367 80
161 93
353 79
301 30
347 53
311 22
81 21
361 97
188 26
329 51
54 18
272 96
188 15
293 67
10 54
167 97
269 18
217 22
245 1
71 99
152 8
149 61
154 93
400 86
166 48
147 4
33 60
342 48
104 92
337 30
334 71
57 7
335 43
381 5
123 58
179 3
277 18
181 78
394 86
34 26
232 73
319 66
336 51
268 67
2 28
329 20
280 91
257 91
354 42
305 55
57 31
49 39
102 99
66 69
10 51
3 37
391 41
246 75
263 72
196 7
161 46
297 12
69 76
189 66
134 5
88 48
346 98
213 32
366 20
313 56
69 90
44 13
307 20
135 85
185 36
237 48
140 61
176 59
392 93
341 74
177 49
70 27
74 32
238 59
269 3
227 59
63 10
201 74
97 82
64 29
374 47
333 32
127 29
152 66
182 52
245 86
45 45
223 30
80 45
377 2
119 32
114 92
340 37
118 38
116 93
360 16
372 48
356 44
333 27
178 21
366 20
140 64
219 95
158 79
157 37
360 73
125 17
347 44
217 56
124 84
347 79
283 23
261 90
236 86
233 17
35 26
176 86
115 30
63 95
338 79
266 9
317 50
335 74
284 69
350 11
285 38
379 14
13 17
72 81
323 95
252 53
161 78
240 13
137 87
69 61
299 80
369 60
27 86
316 63
46 67
384 19
55 46
183 79
155 70
298 68
183 57
94 59
230 47
232 29
360 57
214 36
75 57
287 59
310 43
388 30
155 82
67 53
296 80
284 44
142 10
141 92
27 59
319 57
95 11
108 17
317 62
196 54
235 47
174 2
343 81
192 19
26 75
41 45
293 18
324 25
152 64
66 73
173 46
164 66
82 85
293 34
1 23
178 4
330 99
215 37
315 81
13 87
323 29
96 48
341 67
228 56
329 28
89 75
337 13
213 46
50 5
259 32
214 12
219 29
341 96
141 80
12 29
241 76
164 21
300 14
122 56
158 42
314 41
377 100
162 93
101 21
205 8
54 17
17 4
207 37
138 73
366 96
333 21
385 4
190 26
397 46
264 70
266 28
84 81
365 58
376 92
280 39
266 69
218 91
248 98
79 45
351 16
145 76
343 35
223 11
93 93
73 59
78 57
41 43
299 59
204 65
386 16
17 16
399 29
254 49
133 38
147 34
39 64
150 70
57 28
107 8
396 47
298 9
86 78
255 66
350 49
323 24
103 43
241 14
105 84
283 54
372 84
109 40
180 71
69 22
354 94
204 100
295 66
332 34
320 23
94 62
329 2
109 31
198 86
241 10
60 66
61 64
114 4
161 48
355 92
223 62
231 51
89 6
157 87
207 74
218 77
99 45
293 2
310 59
194 7
400 85
321 75
367 39
12 13
4 33
50 20
207 97
378 84
84 44
80 80
76 87
291 52
292 10
244 9
164 74
192 17
379 18
287 22
166 99
359 19
344 96
362 44
343 59
102 23
134 28
301 54
232 51
180 58
99 86
210 39
235 24
23 26
149 96
215 4
137 67
112 28
292 50
312 68
165 57
167 76
39 21
76 39
398 69
91 57
269 63
244 33
384 63
39 87
65 22
99 99
372 55
192 57
51 1
366 38
115 77
178 90
21 98
4 84
89 42
218 42
192 45
120 61
249 50
137 77
183 50
99 93
51 42
73 99
306 77
169 41
264 92
296 76
246 71
17 44
243 66
344 6
5 65
145 20
52 73
11 84
228 6
341 27
79 88
253 100
110 56
277 8
249 21
282 58
284 22
27 79
321 83
225 36
101 36
70 61
323 62
43 27
3 51
257 72
100 47
1 88
255 36
104 86
238 97
74 86
320 98
226 41
279 57
162 90
228 63
321 15
346 17
217 76
44 17
100 25
78 16
195 10
350 11
278 19
308 80
104 71
303 10
52 75
10 12
351 10
382 80
127 44
323 26
82 15
324 86
6 45
247 72
242 31
190 85
399 93
44 83
340 91
48 99
3 2
57 90
18 11
105 64
360 92
263 5
328 2
396 51
15 86
39 61
74 27
17 91
7 99
162 42
262 11
80 11
118 27
194 66
131 4
366 67
82 66
187 19
213 63
386 14
57 93
167 64
233 50
282 48
161 47
354 99
375 76
220 23
111 22
80 93
308 2
243 19
204 9
253 32
209 95
232 65
86 82
100 12
239 89
296 30
223 6
341 32
252 25
126 89
159 31
179 98
92 55
205 59
46 7
204 30
91 2
162 97
179 89
284 97
237 91
385 65
47 98
365 89
106 64
364 44
161 54
360 5
22 68
179 32
208 90
336 84
252 27
225 11
388 100
157 9
130 86
132 42
184 11
83 81
105 75
242 9
38 57
354 20
278 52
222 10
350 63
187 77
50 33
264 46
156 49
113 80
392 77
115 66
286 67
97 69
8 75
176 71
103 54
292 31
313 52
381 88
80 31
341 73
200 74
130 1
282 2
54 59
367 25
149 3
321 12
290 15
143 13
6 57
83 18
307 74
65 13
352 4
344 61
357 56
179 10
351 91
52 100
298 78
249 100
213 78
2 63
396 29
312 20
259 78
205 64
210 21
158 23
337 18
335 28
220 99
82 18
239 87
123 3
271 69
144 34
275 68
210 70
179 73
33 86
152 80
128 59
236 24
78 91
90 34
95 4
310 15
303 45
41 87
169 78
353 60
16 30
19 47
240 39
237 64
310 9
149 54
347 10
256 83
135 100
360 75
241 33
87 32
44 59
145 78
278 90
313 17
318 81
257 14
245 71
30 42
342 55
54 57
243 73
67 76
210 3
135 94
185 42
104 49
66 40
316 30
313 47
99 78
301 46
245 92
291 60
122 25
158 95
55 89
200 36
145 7
282 88
274 47
271 40
336 21
272 65
396 73
230 43
4 29
209 25
286 98
217 11
45 31
191 53
112 88
374 37
269 20
138 84
138 98
13 59
229 20
310 44
231 12
351 49
6 66
355 2
241 82
111 8
387 97
382 33
288 74
320 46
225 27
68 45
217 88
248 81
272 30
229 40
256 23
195 6
71 1
85 85
117 50
381 11
95 54
214 55
232 13
80 82
364 3
341 64
147 28
191 97
87 9
152 39
120 89
72 70
31 62
14 8
170 37
49 2
1 4
284 69
396 33
128 93
247 100
63 74
333 73
398 64
38 97
385 16
360 15
29 59
34 30
158 40
287 84
235 53
371 51
7 82
10 54
367 79
345 19
20 74
152 3
243 94
167 84
167 41
111 82
354 42
158 65
139 43
75 52
269 51
269 36
48 57
394 76
397 74
225 10
102 41
167 88
95 28
241 20
41 79
275 85
243 38
200 81
78 51
239 41
191 40
143 26
91 29
217 80
25 59
189 27
312 75
128 74
6 57
326 98
67 37
325 2
19 60
237 2
365 89
254 53
275 25
233 3
141 93
102 82
244 57
203 4
354 16
166 32
311 20
79 64
64 6
157 55
313 60
149 71
122 11
141 52
150 84
201 13
358 9
380 4
65 45
274 98
8 10
189 44
326 50
161 11
84 40
391 97
398 27
323 34
137 90
126 73
135 55
175 12
21 79
177 1
209 41
118 46
88 37
68 50
166 1
368 95
119 40
110 92
288 85
121 84
90 15
6 26
176 18
218 70
233 37
66 96
255 24
287 85
176 86
23 18
259 17
288 37
44 71
252 24
389 33
318 78
256 41
4 50
201 60
18 73
145 15
43 83
246 23
167 97
145 4
201 95
377 82
270 43
392 83
42 94
108 1
113 9
295 56
117 63
69 33
195 87
127 24
266 28
156 34
249 11
69 77
48 67
368 21
120 17
154 67
272 50
23 41
108 59
120 93
167 57
138 93
229 21
65 7
327 38
209 11
68 25
301 96
80 7
4 73
117 84
226 15
26 3
209 30
260 100
256 55
340 96
239 38
14 38
191 7
77 39
260 81
17 93
351 51
249 27
124 14
144 13
275 13
248 75
122 15
201 83
269 94
28 54
47 17
20 78
245 10
192 9
34 41
26 32
334 9
300 22
102 65
343 49
49 39
357 38
239 64
129 67
293 100
353 55
280 49
292 34
373 100
286 28
22 73
110 85
11 25
329 19
204 31
294 35
110 98
112 80
61 64
71 40
225 44
206 61
84 4
51 24
356 90
369 81
32 38
198 13
398 28
132 7
268 40
106 60
206 52
110 60
267 23
111 84
16 26
361 53
45 1
132 24
170 67
251 74
2 94
216 44
180 46
353 93
86 6
34 83
277 98
345 100
30 14
194 25
35 85
299 64
190 61
31 3
85 10
291 10
70 91
257 38
284 12
22 16
91 95
17 89
285 37
198 54
92 36
102 31
121 8
319 5
17 82
175 6

Output for test 10

27214