input:

66
5
27 46
89 13
55 8
71 86
22 35
3
3 5
4 7
6 2
2
0 1000000000
1000000000 0
2
1000000000 0
0 1000000000
2
1000000000 0
1000000000 0
2
0 1000000000
0 1000000000
2
1000000000 1000000000
0 0
2
0 0
0 0
2
1000000000 1000000000
1000000000 1000000000
3
90 30
90 50
90 85
3
0 0
0 2
0 5
3
20 30
20 50
20 70
3
...

output:

3
1
0
0
1000000000
1
1000000000
0
0
5
1
21
5
10
3
0
10
5
0
40
0
10
5
10
3
0
10
5
35
146595730144168239
10974087366700578
554139986768573228
183538167814754058
87358691998303367
365292306661444331
23639646046527434
40476687889457528
270663364266559542
139940820548070767
21494649603533736
100200536285...

result:

wrong answer 6th lines differ - expected: '1000000000', found: '1'