3199 - [Sdoi2013]escape

Input

Output

Examples

Input

2
4
10 10 5 5 
5 6
3 5
7 5
5 3
17
14 12 7 6
7 11
6 9
7 7
1 10
2 20
1 6
2 6
1 1
2 2 
5 1
5 2
13 1
12 2
12 7
13 7
12 11
13 11

Output

1
2
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题