B. That bird game
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Examples
Input
2
1 3
6 8
Output
4
Input
5
10 10
1 9
6 12
13 19
4 17
Output
345833344
Input
2
1 1
1 2
Output
666666674