There are three friends named kabir, Rahim and Jamal. They all are good at math. One day Kabir and Rahim are talking about Jamal. He is very arrogant and silent-killer type boy. He observes everything but not replay every time. But he acts like as he knows everything and no-one can defeat him. That's why sometimes Kabir and Rahim called Jamal as Sir. (It's the funny name they gave him). kabir and Rahim decided to accept Jamal as intelligent if he can solve a problem. So they will call him Sir... Sir... Sir...(funny name) if he can solve the following problem. But in order to solve it, Jamal needs your help. Can you help him out?
Given an infinite 2D grid with the top left cell. It referenced as (1,1) cell. All the cells contain a value of zero initially. Let's play a game?
The game consists of N steps where in each step you are given two integers a and b. The value of each of the cells in the co-ordinate (u, v) satisfying 1 ≤ u ≤ a and 1 ≤ v ≤ b, is increased by 1. After N such steps, if X is the largest number amongst all the cells in the rectangular board, can you print the number of X's on the board and the difference between the summation of maximum values and the summation of all grid.
Input
The first line of input contains a single integer 1<= T <=31. T denote test case. The second line of input contains a single integer 1<= N <=100. N lines follow. Each line contains two integers 1<= a <=10^8 and 1<= b <=10^8 separated by a single space.
Output
For each test print the case number first.
Then Output an integer - the number of X's. And the difference between the summation of maximum values and the summation of all grid.Print the absolute value.
Sample
| Input | Output |
|---|---|
1 3 2 3 3 3 2 2 | Case 1: 4 7 |
Explanation
Assume that the following board corresponds to cells (i, j) where 1 ≤ i ≤ 3 and 1 ≤ j ≤ 3.
At the beginning, all the 3*3 grids are 0.
After the first step we will obtain:
1 1 1
1 1 1
0 0 0
After the second step we will obtain:
2 2 2
2 2 2
1 1 1
Finally, after the last step we will obtain:
3 3 2
3 3 2
1 1 1
So, the maximum number is 3 and there are exactly four cells which correspond to 3. And the difference between the summation of maximum values and the summation of all grid = 7.
