DWITE Contest

Test Case for Question #3 in DWITE 2011-2012 High School Round 4

Contest: DWITE 2011-2012 High School Round 4
Question: #3
Input File: DATA3.txt
Output File: OUT3.txt


Input

36 55
1 13
2 14
3 15
4 16
5 17
6 18
7 19
8 20
9 21
10 22
11 23
12 24
13 25
14 26
15 27
16 28
17 29
18 30
19 31
20 32
21 33
22 34
23 35
24 36
8 20
1 2
1 3
1 4
1 5
1 6
2 3
3 4
4 5
5 6
6 2
7 8
7 9
7 10
7 11
7 12
8 9
9 10
10 11
11 12
12 8
2 8
8 3
3 9
9 4
4 10
10 5
5 11
11 6
6 12
12 2
27 31
1 2
2 3
3 4
4 5
5 6
6 7
6 1
5 8
8 9
9 10
10 11
11 6
11 12
12 13
13 14
14 15
14 16
16 10
16 17
17 18
18 19
19 14
19 20
20 21
20 22
22 23
23 24
24 25
25 26
25 27
8 5
555 1000
2 1
3 2
4 2
5 1
6 5
7 5
8 6
9 7
10 8
11 5
12 8
13 6
14 12
15 14
16 2
17 12
18 4
19 9
20 2
21 17
22 10
23 19
24 16
25 10
26 18
27 7
28 7
29 13
30 28
31 6
32 23
33 31
34 21
35 13
36 15
37 5
38 27
39 4
40 32
41 15
42 4
43 40
44 19
45 18
46 34
47 19
48 8
49 32
50 30
51 19
52 48
53 33
54 15
55 34
56 18
57 36
58 3
59 56
60 36
61 59
62 56
63 60
64 15
65 51
66 29
67 11
68 63
69 35
70 14
71 39
72 41
73 46
74 50
75 70
76 71
77 75
78 69
79 58
80 62
81 29
82 28
83 78
84 15
85 47
86 57
87 59
88 8
89 73
90 48
91 29
92 19
93 56
94 75
95 44
96 28
97 35
98 17
99 25
100 61
101 42
102 87
103 6
104 5
105 19
106 25
107 73
108 68
109 39
110 64
111 57
112 27
113 74
114 31
115 35
116 61
117 30
118 102
119 116
120 100
121 73
122 29
123 115
124 60
125 37
126 106
127 72
128 34
129 87
130 33
131 93
132 103
133 95
134 51
135 17
136 62
137 31
138 9
139 108
140 77
141 138
142 89
143 76
144 12
145 16
146 11
147 4
148 17
149 139
150 84
151 139
152 81
153 19
154 120
155 95
156 139
157 153
158 116
159 44
160 1
161 56
162 23
163 42
164 78
165 38
166 99
167 10
168 41
169 10
170 54
171 41
172 32
173 49
174 33
175 59
176 47
177 86
178 91
179 60
180 158
181 5
182 137
183 3
184 54
185 160
186 149
187 39
188 169
189 29
190 173
191 88
192 100
193 110
194 138
195 174
196 63
197 70
198 127
199 84
200 128
201 115
202 39
203 143
204 57
205 112
206 101
207 100
208 167
209 149
210 18
211 64
212 106
213 197
214 94
215 82
216 155
217 87
218 158
219 212
220 28
221 44
222 26
223 34
224 102
225 96
226 24
227 115
228 66
229 7
230 200
231 17
232 15
233 202
234 18
235 207
236 45
237 18
238 91
239 61
240 136
241 53
242 14
243 222
244 209
245 134
246 119
247 42
248 56
249 73
250 233
251 12
252 139
253 115
254 238
255 244
256 184
257 119
258 149
259 243
260 228
261 94
262 116
263 231
264 175
265 97
266 152
267 79
268 177
269 160
270 69
271 30
272 35
273 189
274 47
275 4
276 126
277 225
278 108
279 9
280 79
281 270
282 159
283 25
284 101
285 134
286 151
287 122
288 124
289 218
290 196
291 136
292 26
293 183
294 197
295 238
296 98
297 149
298 12
299 69
300 8
301 90
302 111
303 224
304 248
305 117
306 76
307 152
308 58
309 226
310 26
311 213
312 290
313 277
314 122
315 300
316 75
317 100
318 113
319 239
320 100
321 50
322 80
323 50
324 164
325 314
326 194
327 50
328 28
329 81
330 322
331 266
332 326
333 15
334 135
335 17
336 25
337 278
338 313
339 54
340 24
341 24
342 222
343 74
344 316
345 102
346 223
347 83
348 98
349 66
350 126
351 107
352 242
353 199
354 349
355 17
356 127
357 229
358 349
359 175
360 309
361 2
362 121
363 179
364 284
365 275
366 365
367 66
368 236
369 312
370 280
371 45
372 185
373 123
374 270
375 80
376 62
377 42
378 328
379 51
380 274
381 339
382 119
383 356
384 341
385 96
386 193
387 152
388 162
389 147
390 368
391 85
392 10
393 3
394 7
395 66
396 379
397 351
398 342
399 40
400 337
401 178
402 130
403 111
404 152
405 245
406 183
407 182
408 254
409 321
410 175
411 248
412 282
413 392
414 379
415 142
416 299
417 261
418 182
419 295
420 73
421 322
422 271
423 3
424 163
425 34
426 201
427 252
428 380
429 143
430 63
431 327
432 135
433 125
434 136
435 115
436 229
437 19
438 287
439 263
440 236
441 34
442 308
443 125
444 291
445 228
446 166
447 63
448 141
449 255
450 2
451 25
452 58
453 318
454 303
455 357
456 364
457 311
458 6
459 25
460 89
461 54
462 341
463 75
464 93
465 161
466 195
467 319
468 466
469 304
470 107
471 47
472 62
473 38
474 7
475 408
476 77
477 240
478 119
479 293
480 459
481 310
482 187
483 217
484 103
485 100
486 478
487 381
488 191
489 252
490 251
491 79
492 383
493 477
494 1
495 143
496 124
497 293
498 259
499 314
500 216
501 26
502 263
503 229
504 167
505 53
506 486
507 87
508 113
509 292
510 304
511 48
512 203
513 17
514 37
515 19
516 319
517 92
518 288
519 132
520 498
521 310
522 162
523 488
524 131
525 287
526 491
527 384
528 411
529 145
530 138
531 80
532 180
533 525
534 170
535 189
536 58
537 285
538 171
539 362
540 398
541 171
542 395
543 207
544 505
545 185
546 331
547 535
548 480
549 209
550 209
551 457
552 12
553 95
554 22
555 82
22 462
517 478
202 38
478 517
5 502
132 258
203 123
508 382
486 177
4 265
365 126
455 53
97 441
399 313
255 320
550 323
368 495
333 189
388 264
357 536
78 94
236 174
4 498
445 407
542 196
370 66
447 111
517 300
221 149
541 194
80 502
539 525
528 450
7 329
187 176
303 4
342 301
539 547
431 436
378 363
417 353
445 489
88 129
547 464
51 434
321 93
54 56
463 503
363 171
405 522
61 404
381 221
73 370
461 161
484 445
337 101
400 159
336 435
93 391
290 527
199 500
466 74
433 448
345 142
32 548
363 127
45 161
64 315
67 528
236 359
444 128
295 52
83 220
451 344
278 200
86 472
514 551
183 538
415 504
132 464
157 144
131 527
295 481
510 13
405 379
377 45
184 353
196 231
536 430
304 323
9 148
265 329
197 105
159 531
456 408
342 364
105 278
195 111
540 405
91 226
491 534
14 121
167 19
43 53
513 113
266 349
487 454
549 198
501 330
141 16
29 454
373 424
169 428
210 379
55 242
479 243
54 426
132 94
540 354
272 136
180 79
341 91
194 428
97 249
276 37
201 379
419 100
125 209
499 30
68 347
505 526
9 537
437 491
376 477
350 62
270 81
205 33
306 154
48 117
304 98
447 177
89 10
215 46
92 398
506 124
471 497
307 282
290 445
487 548
72 314
503 246
481 22
471 82
196 347
448 302
266 541
113 545
349 364
327 133
134 48
34 460
209 540
219 382
149 25
108 329
470 164
341 546
229 209
186 291
282 280
249 347
229 270
473 232
185 529
173 334
150 1
408 264
502 500
549 280
139 420
107 34
301 347
420 183
496 339
39 40
513 389
168 306
382 130
299 527
75 389
406 295
518 10
59 271
97 180
133 121
136 46
16 265
243 429
333 290
546 176
65 355
56 401
422 437
356 15
461 369
319 234
113 373
542 385
29 19
177 251
59 274
29 210
359 541
77 221
330 517
234 113
69 421
534 291
242 90
346 379
535 254
247 111
127 40
28 419
40 95
7 81
502 157
302 532
362 228
487 540
231 137
472 8
292 515
450 436
143 459
475 77
1 128
119 337
367 59
439 53
273 443
172 458
47 546
250 170
200 247
81 204
27 293
500 371
279 249
277 393
137 145
345 189
303 290
336 498
295 265
479 339
169 322
455 309
182 107
248 549
504 368
37 78
273 41
103 44
498 283
214 81
433 171
64 265
38 469
8 541
11 136
438 133
137 83
339 473
299 532
177 366
10 276
104 230
101 396
146 163
188 546
141 238
162 120
304 392
390 307
99 145
314 469
91 96
422 476
76 549
470 361
351 30
133 103
287 555
340 265
331 289
46 459
171 366
313 242
23 169
184 422
190 415
512 525
266 286
18 15
243 404
360 536
79 44
412 426
273 59
348 425
442 517
92 358
145 211
315 505
389 422
277 310
95 16
476 371
122 371
506 390
520 287
244 535
190 331
271 139
50 397
93 209
164 502
184 2
206 433
250 455
386 243
298 417
511 215
320 255
473 506
21 475
313 182
38 18
488 355
76 226
400 181
249 200
262 458
18 130
109 363
328 418
544 531
244 19
105 350
210 72
435 404
396 167
397 386
268 488
143 228
32 450
118 27
524 138
472 157
279 309
514 223
374 347
341 32
548 547
66 46
440 382
253 430
544 320
138 469
544 347
7 14
179 513
12 332
153 408
389 483
309 551
74 526
269 373
359 224
302 526
154 447
341 400
93 345
330 127
271 288
509 369
320 498
438 76
482 138
183 3
241 148
490 272
496 499
18 254
545 501
190 108
388 231
433 514
157 53
6 339
102 39
554 426
254 197
523 286
33 469
120 292
184 174
438 446
394 217
378 551
310 284
154 442
534 12
273 299
65 11
261 441
372 277
64 36
11 519
49 78
224 531
107 71
386 500
183 248
348 114
493 270
165 150
504 373
548 228
101 549
490 168
489 455
371 202
190 6
388 124
89 427
55 329
477 6
430 1
168 480
21 379
167 355
11 168
345 326
159 544
750 1000
2 1
3 2
4 2
5 4
6 1
7 1
8 7
9 2
10 5
11 10
12 4
13 2
14 10
15 9
16 11
17 14
18 6
19 16
20 2
21 18
22 11
23 20
24 11
25 18
26 2
27 25
28 27
29 3
30 7
31 30
32 21
33 26
34 28
35 16
36 10
37 1
38 21
39 29
40 5
41 9
42 41
43 24
44 20
45 4
46 22
47 23
48 46
49 36
50 8
51 12
52 41
53 47
54 53
55 52
56 22
57 53
58 31
59 16
60 58
61 34
62 57
63 43
64 26
65 8
66 50
67 26
68 37
69 57
70 22
71 13
72 46
73 41
74 14
75 40
76 57
77 7
78 11
79 7
80 49
81 4
82 7
83 52
84 74
85 44
86 72
87 27
88 19
89 59
90 52
91 39
92 5
93 55
94 58
95 42
96 47
97 20
98 60
99 79
100 34
101 100
102 69
103 62
104 4
105 89
106 83
107 8
108 77
109 63
110 32
111 106
112 92
113 38
114 109
115 23
116 17
117 83
118 39
119 45
120 43
121 118
122 110
123 27
124 94
125 44
126 95
127 107
128 19
129 102
130 62
131 66
132 95
133 62
134 26
135 57
136 102
137 120
138 35
139 39
140 85
141 16
142 60
143 17
144 8
145 114
146 21
147 56
148 15
149 86
150 63
151 79
152 118
153 5
154 22
155 70
156 121
157 15
158 146
159 60
160 106
161 70
162 114
163 96
164 47
165 63
166 113
167 43
168 46
169 72
170 131
171 123
172 5
173 98
174 139
175 100
176 56
177 144
178 127
179 131
180 27
181 8
182 136
183 1
184 134
185 184
186 35
187 105
188 178
189 27
190 54
191 129
192 10
193 61
194 111
195 138
196 149
197 156
198 27
199 58
200 29
201 56
202 128
203 89
204 24
205 114
206 77
207 120
208 147
209 120
210 64
211 35
212 173
213 20
214 88
215 63
216 190
217 159
218 140
219 98
220 134
221 76
222 97
223 29
224 126
225 17
226 23
227 205
228 178
229 143
230 39
231 82
232 14
233 48
234 119
235 156
236 77
237 190
238 41
239 160
240 21
241 195
242 105
243 154
244 210
245 140
246 5
247 153
248 119
249 106
250 201
251 30
252 193
253 97
254 68
255 64
256 88
257 11
258 224
259 34
260 257
261 133
262 75
263 151
264 22
265 120
266 119
267 122
268 119
269 47
270 2
271 47
272 72
273 215
274 121
275 258
276 221
277 235
278 18
279 55
280 257
281 65
282 168
283 215
284 110
285 40
286 97
287 253
288 272
289 51
290 208
291 208
292 183
293 155
294 257
295 26
296 32
297 256
298 244
299 149
300 33
301 214
302 25
303 46
304 16
305 237
306 112
307 230
308 99
309 201
310 12
311 248
312 7
313 44
314 218
315 56
316 223
317 252
318 125
319 242
320 108
321 18
322 175
323 217
324 81
325 83
326 294
327 9
328 121
329 81
330 214
331 48
332 249
333 141
334 30
335 264
336 158
337 158
338 288
339 23
340 140
341 222
342 34
343 10
344 241
345 283
346 123
347 96
348 344
349 181
350 78
351 196
352 188
353 302
354 82
355 188
356 258
357 275
358 87
359 122
360 336
361 81
362 197
363 27
364 358
365 246
366 164
367 324
368 59
369 304
370 356
371 21
372 368
373 286
374 281
375 94
376 260
377 334
378 39
379 206
380 110
381 95
382 101
383 96
384 20
385 145
386 361
387 322
388 202
389 365
390 334
391 187
392 129
393 193
394 46
395 197
396 266
397 179
398 257
399 73
400 333
401 237
402 372
403 249
404 31
405 385
406 76
407 303
408 105
409 78
410 379
411 347
412 336
413 54
414 100
415 187
416 96
417 257
418 49
419 290
420 330
421 87
422 353
423 379
424 215
425 209
426 266
427 227
428 427
429 154
430 134
431 77
432 250
433 187
434 363
435 309
436 22
437 47
438 41
439 51
440 118
441 89
442 345
443 433
444 374
445 415
446 221
447 272
448 41
449 392
450 365
451 141
452 332
453 244
454 114
455 276
456 7
457 18
458 454
459 52
460 166
461 290
462 314
463 113
464 326
465 132
466 261
467 437
468 29
469 77
470 110
471 180
472 400
473 457
474 40
475 135
476 281
477 104
478 164
479 456
480 377
481 397
482 160
483 275
484 435
485 275
486 94
487 411
488 52
489 378
490 371
491 51
492 53
493 466
494 292
495 39
496 30
497 47
498 341
499 216
500 35
501 197
502 477
503 81
504 361
505 124
506 339
507 117
508 120
509 170
510 313
511 236
512 55
513 504
514 105
515 51
516 227
517 426
518 74
519 438
520 104
521 179
522 503
523 229
524 51
525 180
526 29
527 335
528 344
529 468
530 266
531 185
532 273
533 288
534 5
535 197
536 512
537 532
538 304
539 306
540 176
541 326
542 110
543 140
544 149
545 496
546 392
547 281
548 87
549 108
550 507
551 356
552 88
553 459
554 349
555 493
556 499
557 423
558 481
559 344
560 209
561 219
562 145
563 373
564 375
565 31
566 310
567 96
568 113
569 199
570 103
571 62
572 47
573 562
574 147
575 505
576 381
577 415
578 372
579 546
580 278
581 497
582 522
583 120
584 521
585 356
586 56
587 48
588 512
589 463
590 254
591 139
592 143
593 203
594 492
595 49
596 179
597 280
598 168
599 592
600 508
601 7
602 372
603 454
604 42
605 228
606 87
607 133
608 405
609 12
610 100
611 594
612 505
613 237
614 219
615 173
616 438
617 165
618 36
619 184
620 215
621 452
622 64
623 404
624 486
625 62
626 44
627 303
628 256
629 185
630 409
631 238
632 362
633 267
634 491
635 163
636 157
637 150
638 167
639 36
640 316
641 575
642 638
643 382
644 616
645 332
646 531
647 10
648 13
649 462
650 190
651 282
652 515
653 274
654 16
655 168
656 386
657 236
658 276
659 181
660 655
661 540
662 432
663 480
664 159
665 555
666 428
667 529
668 150
669 558
670 316
671 269
672 485
673 352
674 24
675 571
676 69
677 590
678 672
679 572
680 133
681 662
682 473
683 163
684 183
685 14
686 604
687 425
688 146
689 43
690 72
691 656
692 105
693 35
694 474
695 279
696 546
697 46
698 220
699 613
700 567
701 423
702 651
703 103
704 192
705 407
706 259
707 46
708 673
709 264
710 521
711 598
712 392
713 575
714 230
715 128
716 473
717 262
718 496
719 612
720 690
721 244
722 488
723 114
724 125
725 673
726 34
727 558
728 460
729 670
730 597
731 33
732 504
733 656
734 295
735 192
736 626
737 685
738 375
739 236
740 433
741 416
742 41
743 448
744 329
745 496
746 329
747 436
748 282
749 707
750 351
301 705
79 586
8 584
144 741
354 251
734 223
272 112
241 339
642 9
298 103
659 480
553 434
241 253
569 673
396 136
9 362
243 445
450 689
679 293
608 692
348 720
596 631
414 715
211 562
636 574
505 463
454 353
570 655
530 53
575 400
731 745
345 300
619 66
114 53
274 471
482 748
12 620
149 749
354 353
180 304
294 273
339 64
335 101
523 491
162 493
402 81
478 617
627 429
721 366
599 549
680 136
358 634
163 153
513 671
271 273
274 342
687 389
168 218
393 199
18 500
66 640
183 120
332 504
631 279
632 340
653 631
423 365
408 296
679 432
491 361
678 322
487 460
394 341
634 38
644 131
25 244
283 704
212 41
163 558
748 402
424 641
218 641
204 317
384 412
160 246
137 402
516 102
341 710
748 284
1 59
172 176
582 538
272 538
250 505
230 639
201 531
212 119
206 41
79 460
373 149
11 99
186 732
615 68
494 97
412 247
39 171
289 477
556 168
622 261
503 259
434 6
566 727
152 35
10 644
549 274
43 444
184 138
604 691
462 195
669 378
749 240
249 130
398 650
182 670
126 99
700 687
600 624
694 232
155 362
685 386
718 317
144 205
617 204
309 474
685 43
168 299
220 431
62 315
341 178
494 105
100 725
446 507
659 340
109 60
640 198
41 69
365 726
27 340
254 67
163 91
571 427
646 142
737 402
110 688
584 86
141 501
687 256
132 379
3 278
113 175
566 123
83 136
179 647
640 479
384 176
266 511
546 529
572 356
271 178
24 385
252 176
587 585
2 488
311 725
91 107
322 581
436 646
33 326
719 74
213 288
499 156
413 218
443 40
298 447
354 232
116 90
359 580
396 395
700 146
23 676
113 573
274 231
739 648
543 359
454 28
126 635
652 79
383 670
487 479
690 139
722 677
164 178
576 725
482 701
462 363
253 449
346 685
17 138
508 494
285 695
260 72
309 644
419 178
120 608
542 642
515 124
166 573
680 92
216 366
537 708
10 701
703 594
242 580
449 728
549 475
575 275
134 386
39 171
113 380
585 660
629 174
86 151
525 694
606 413
16 518
408 178
285 705
541 85
392 622
86 735
441 293
749 337
519 622
425 98
377 255
420 109
178 494
569 367
103 189
601 320
69 41
963 1000
2 1
3 2
4 1
5 1
6 3
7 5
8 5
9 4
10 4
11 5
12 7
13 4
14 7
15 1
16 2
17 15
18 9
19 13
20 1
21 5
22 3
23 17
24 18
25 2
26 9
27 2
28 27
29 23
30 15
31 16
32 6
33 27
34 2
35 28
36 16
37 24
38 33
39 10
40 36
41 24
42 41
43 13
44 34
45 41
46 17
47 35
48 24
49 8
50 33
51 39
52 9
53 21
54 49
55 16
56 40
57 32
58 17
59 48
60 2
61 22
62 22
63 26
64 47
65 8
66 1
67 32
68 31
69 39
70 40
71 34
72 61
73 3
74 58
75 32
76 4
77 1
78 59
79 10
80 35
81 10
82 17
83 13
84 45
85 62
86 3
87 39
88 35
89 25
90 1
91 85
92 42
93 13
94 17
95 69
96 35
97 96
98 94
99 49
100 27
101 72
102 51
103 62
104 82
105 68
106 20
107 66
108 26
109 68
110 109
111 13
112 34
113 92
114 101
115 87
116 39
117 41
118 4
119 44
120 79
121 60
122 98
123 90
124 79
125 43
126 68
127 122
128 38
129 77
130 40
131 35
132 75
133 86
134 97
135 120
136 117
137 75
138 33
139 109
140 110
141 95
142 106
143 132
144 127
145 54
146 2
147 87
148 145
149 148
150 117
151 11
152 144
153 114
154 20
155 84
156 104
157 21
158 38
159 37
160 105
161 55
162 13
163 78
164 61
165 109
166 15
167 109
168 165
169 89
170 116
171 81
172 72
173 117
174 113
175 73
176 80
177 32
178 1
179 52
180 4
181 46
182 128
183 151
184 139
185 122
186 34
187 183
188 44
189 13
190 86
191 188
192 94
193 132
194 96
195 1
196 57
197 118
198 12
199 173
200 145
201 93
202 105
203 197
204 125
205 138
206 182
207 150
208 7
209 3
210 23
211 72
212 172
213 188
214 49
215 178
216 135
217 84
218 140
219 51
220 187
221 209
222 72
223 160
224 148
225 62
226 29
227 128
228 7
229 60
230 178
231 96
232 221
233 127
234 149
235 134
236 58
237 51
238 208
239 118
240 27
241 118
242 157
243 95
244 164
245 100
246 88
247 40
248 147
249 32
250 39
251 156
252 54
253 116
254 88
255 135
256 91
257 108
258 163
259 249
260 169
261 79
262 144
263 121
264 19
265 96
266 65
267 143
268 178
269 227
270 20
271 170
272 237
273 194
274 1
275 108
276 167
277 229
278 68
279 174
280 20
281 111
282 147
283 69
284 135
285 87
286 48
287 135
288 241
289 247
290 35
291 147
292 156
293 252
294 174
295 270
296 117
297 118
298 117
299 275
300 74
301 286
302 164
303 264
304 144
305 61
306 74
307 109
308 59
309 167
310 81
311 200
312 32
313 88
314 279
315 26
316 229
317 161
318 289
319 271
320 132
321 70
322 162
323 64
324 295
325 302
326 261
327 197
328 305
329 132
330 309
331 297
332 113
333 213
334 106
335 246
336 150
337 161
338 32
339 88
340 323
341 58
342 305
343 89
344 1
345 11
346 269
347 39
348 197
349 26
350 45
351 210
352 5
353 65
354 132
355 41
356 170
357 69
358 262
359 207
360 244
361 175
362 254
363 20
364 127
365 334
366 114
367 58
368 197
369 70
370 108
371 304
372 58
373 279
374 208
375 19
376 285
377 297
378 280
379 165
380 151
381 355
382 45
383 364
384 80
385 209
386 323
387 74
388 101
389 150
390 7
391 3
392 243
393 177
394 271
395 201
396 390
397 244
398 154
399 260
400 149
401 338
402 386
403 235
404 107
405 154
406 242
407 378
408 359
409 361
410 393
411 14
412 361
413 186
414 97
415 94
416 291
417 156
418 69
419 75
420 330
421 136
422 318
423 137
424 52
425 233
426 337
427 293
428 158
429 256
430 23
431 327
432 400
433 351
434 372
435 352
436 63
437 49
438 220
439 233
440 144
441 371
442 159
443 221
444 214
445 418
446 70
447 141
448 271
449 76
450 76
451 405
452 109
453 111
454 24
455 389
456 237
457 16
458 134
459 442
460 168
461 376
462 82
463 426
464 438
465 101
466 285
467 157
468 368
469 190
470 123
471 240
472 196
473 128
474 144
475 346
476 78
477 268
478 397
479 290
480 478
481 169
482 21
483 68
484 10
485 196
486 463
487 135
488 20
489 332
490 302
491 316
492 268
493 251
494 356
495 129
496 32
497 426
498 20
499 96
500 311
501 216
502 214
503 180
504 44
505 247
506 331
507 83
508 327
509 490
510 433
511 259
512 489
513 250
514 35
515 349
516 257
517 489
518 230
519 385
520 493
521 143
522 457
523 301
524 176
525 45
526 447
527 72
528 287
529 424
530 247
531 144
532 279
533 444
534 142
535 107
536 357
537 376
538 426
539 525
540 339
541 531
542 96
543 471
544 485
545 167
546 457
547 278
548 222
549 161
550 33
551 270
552 37
553 257
554 292
555 520
556 460
557 295
558 241
559 498
560 243
561 166
562 488
563 91
564 263
565 237
566 158
567 211
568 49
569 491
570 507
571 188
572 120
573 15
574 571
575 314
576 51
577 408
578 247
579 209
580 561
581 385
582 91
583 433
584 160
585 552
586 114
587 154
588 138
589 388
590 520
591 429
592 137
593 45
594 38
595 297
596 560
597 99
598 179
599 427
600 333
601 81
602 17
603 473
604 316
605 483
606 386
607 238
608 79
609 374
610 410
611 177
612 253
613 583
614 78
615 344
616 112
617 118
618 449
619 139
620 598
621 16
622 564
623 155
624 518
625 484
626 313
627 259
628 627
629 622
630 514
631 565
632 444
633 249
634 477
635 288
636 388
637 490
638 22
639 62
640 595
641 104
642 587
643 368
644 77
645 522
646 164
647 599
648 397
649 259
650 178
651 445
652 239
653 152
654 193
655 265
656 108
657 355
658 170
659 270
660 610
661 339
662 386
663 407
664 494
665 652
666 112
667 407
668 601
669 412
670 13
671 562
672 50
673 342
674 273
675 244
676 488
677 70
678 572
679 88
680 461
681 485
682 615
683 520
684 597
685 319
686 255
687 397
688 228
689 498
690 450
691 223
692 356
693 485
694 199
695 604
696 370
697 185
698 53
699 515
700 674
701 550
702 191
703 80
704 553
705 105
706 457
707 126
708 656
709 576
710 398
711 510
712 117
713 286
714 294
715 503
716 130
717 45
718 2
719 396
720 365
721 618
722 235
723 425
724 33
725 480
726 599
727 50
728 205
729 152
730 697
731 164
732 410
733 283
734 47
735 485
736 4
737 456
738 280
739 556
740 72
741 139
742 509
743 170
744 31
745 310
746 20
747 58
748 329
749 339
750 700
751 70
752 681
753 546
754 268
755 159
756 282
757 401
758 408
759 445
760 103
761 289
762 70
763 136
764 638
765 175
766 147
767 113
768 286
769 667
770 313
771 408
772 357
773 483
774 160
775 696
776 132
777 83
778 89
779 265
780 744
781 652
782 676
783 81
784 231
785 530
786 62
787 374
788 28
789 571
790 566
791 432
792 569
793 125
794 161
795 596
796 116
797 251
798 168
799 160
800 545
801 586
802 417
803 605
804 342
805 217
806 573
807 586
808 556
809 407
810 534
811 29
812 345
813 48
814 274
815 280
816 164
817 435
818 547
819 599
820 753
821 30
822 204
823 443
824 69
825 347
826 155
827 239
828 200
829 62
830 580
831 697
832 699
833 766
834 166
835 84
836 338
837 524
838 544
839 436
840 753
841 793
842 256
843 823
844 39
845 668
846 16
847 841
848 193
849 284
850 508
851 207
852 62
853 123
854 316
855 677
856 52
857 331
858 397
859 606
860 603
861 480
862 257
863 482
864 418
865 286
866 44
867 207
868 23
869 380
870 250
871 382
872 564
873 706
874 534
875 415
876 810
877 55
878 107
879 662
880 708
881 422
882 88
883 236
884 123
885 645
886 568
887 616
888 756
889 350
890 491
891 536
892 759
893 197
894 816
895 628
896 373
897 275
898 681
899 514
900 8
901 54
902 585
903 695
904 290
905 849
906 781
907 231
908 473
909 33
910 530
911 268
912 598
913 247
914 305
915 12
916 421
917 592
918 532
919 238
920 448
921 283
922 90
923 600
924 439
925 506
926 409
927 859
928 347
929 484
930 710
931 599
932 780
933 533
934 920
935 774
936 618
937 270
938 441
939 608
940 776
941 730
942 354
943 55
944 833
945 89
946 748
947 823
948 553
949 133
950 601
951 714
952 155
953 194
954 571
955 867
956 585
957 786
958 394
959 139
960 369
961 665
962 813
963 760
905 860
21 772
829 727
896 204
617 463
399 825
86 307
53 138
267 491
152 436
155 117
49 542
347 728
822 364
936 23
262 122
593 429
330 3
754 894
9 947
906 890
185 692
27 239
164 579
72 721
443 595
576 684
206 135
85 129
842 221
913 166
211 939
727 305
933 724
878 871
424 368
212 509
635 444




Output

23
10
56
237
780