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
-5
-3
-2
-10
2
1
6
6
7
0
2
-7
-8
-708
-24973085279109
24978140601872
41095353522
-62281404535

result:

wrong answer 3rd lines differ - expected: '-2', found: '-5'