input:

20
3
0 2
1 2
3 3
3
1 0
2 3
0 4
4
2 8
1 14
10 2
10 6
2
1 3
3 4
2
4 8
6 2
2
0 0
10 10
2
5 0
2 1
2
4 5
6 2
3
4 2
10 9
3 8
3
6 1
3 4
4 0
3
10 3
7 3
2 10
3
1 9
8 1
0 0
4
1 2
15 8
11 8
10 2
4
9 3
5 14
10 5
2 12
4
7 6
7 6
12 11
2 15
100000
3 1
10 8
1 8
7 9
3 6
9 2
0 7
1 3
7 1
2 0
10 9
2 5
0 3
6 1
9 0
1 1
1...

output:

1
-1
-2
0
2
10
4
2
6
6
7
0
15
-1
-2
-697
-24972584309703
24978641064563
42097360102
-61290555356

result:

ok 20 lines