As the owner of a vast collection of fine ladders, you would like to display them to potential onlookers. You've decided to stand your N ladders up vertically, with their bases at distinct points on a horizontal number line. The ith ladder's base is at position Xi, and it has height Hi.
The local snake population has taken an interest in your ladders. As everyone knows, snakes love nothing more than to suspend themselves horizontally above the ground! In particular, a snake of length L is able to suspend itself between the tops of two ladders a and b if and only if they meet the following conditions:
- the ladders are exactly L units apart (|Xa - Xb| = L)
- the ladders are of equal height (Ha = Hb)
- there are no taller ladders in between them (there exists no ladder c such that min{Xa, Xb} < Xc < max{Xa, Xb} and Hc > Ha)
A number of snakes are planning to take up residence amongst your ladders. In particular, for every position in which a snake could suspend itself (in other words, for every distinct, unordered pair of ladders a and b), one snake will move in of the appropriate length.
You'll have no choice but to take care of these snakes, of course. To feed a snake of length L, it'll cost you L^2 dollars daily. To prepare your budget, you'd like to calculate how many dollars you'll be spending each day on your new pets!
Input
Input begins with an integer T, the number of sets of ladders you own. For each set, there is first a line containing the integer N. Then, N lines follow, the ith of which contains two space-separated integers, Xi and Hi.
Output
For the ith set of ladders, print a line containing "Case #i: " followed by the daily feeding cost of all the snakes that move in, modulo 10^9 + 7.
Constraints
1 ≤ T ≤ 50
1 ≤ N ≤ 200,000
0 ≤ Xi, Hi ≤ 1,000,000,000
Explanation of Sample
In the first case, one snake will move in between your two ladders. It will have length 20, so it will cost 20^2 = 400 dollars a day to feed. In the third case, one snake will move in between the ladders of height 3, and another will move in between the ladders at X = 2 and X = 3. The first snake has length 3, and the second has length 1. The total cost is therefore 3^2 + 1^2 = 10.
Sample inlet
Code: Select all
5
2
10 100
30 100
3
10 100
30 100
40 100
5
1 3
4 3
3 2
5 2
2 2
8
5 6
8 1
9 5
13 5
15 6
16 6
19 7
100 6
4
1 1000000000
1000 1000000000
1000000 1000000000
1000000000 1000000000Code: Select all
Case #1: 400
Case #2: 1400
Case #3: 10
Case #4: 238
Case #5: 14991178