Read problems statements in mandarin chinese, russian and vietnamese as well.

Yesterday Chef had cooked N very tasty dishes. A dish is prepared of several ingredients. You are given this information by N arrays, each array contains elements equal to the number of ingredients used in that dish. Also, an element of the array denotes the tastiness of the ingredient in the corresponding dish.

Chef placed his N dishes in a line, one after the other. You can make a simple observation that the last ingredient of a dish will be a neighbor of the first ingredient of the next dish. Of course, this is not valid for the N-th dish, as it's the last dish.

Overall quality of these dishes will be calculated as follows. Consider dish i and i + 1, if the last ingredient of dish i be of tastiness x, and the first ingredient of dish i + 1 of tastiness of y, then the quality of dish will be increased by |x - y| * i, where (|t| denotes the absolute value of t).

Chef wants to maximize the quality of the dish. For each dish, he is allowed to take its ingredients and cyclically rotate/shift them by as many rotations as he wishes. Find the maximum possible quality of the dishes that he can obtain.

------ Input ------

The first line of the input contains an integer T denoting the number of test cases.
The first line of each test case contains a single integer N denoting the number of dishes.
Next N lines follows. i-th line contains integer M denoting the number of ingredients in i-th dish and M space-separated integers A_{1}, A_{2}, ..., A_{M} denoting the tastiness of ingredients of i-th dish.".

------ Output ------

For each test case, output in a single line an integer corresponding to the maximum possible quality of the dishes.

------ Constraints ------

$Total number of ingredients over all the test cases in a single test file won't exceed 10^{6}$
$M ≥ 1$
$1 ≤ A_{i} ≤ 10^{6}$

------ Subtasks ------

$Subtask #1 (20 points): Total number of dishes = 2.$
$Subtask #2 (30 points): 1 ≤ A_{i} ≤ 500$
$Subtask #3 (50 points): original constraints$

------ Example ------

Input:
3
3
3 1 2 3
2 3 2
2 4 5
2
2 1 2
2 4 5
3
2 1 2
3 3 2 5
2 4 5

Output:
8
4
10

------ Explanation ------

Example case 1.
01) 123|32|45 = 0 * 1 + 2 * 2 = 4
02) 312|32|45 = 1 * 1 + 2 * 2 = 5
03) 231|32|45 = 2 * 1 + 2 * 2 = 6
04) 123|23|45 = 1 * 1 + 1 * 2 = 3
05) 312|23|45 = 0 * 1 + 1 * 2 = 2
06) 231|23|45 = 1 * 1 + 1 * 2 = 3
07) 123|32|54 = 0 * 1 + 3 * 2 = 6
08) 312|32|54 = 1 * 1 + 3 * 2 = 7
09) 231|32|54 = 2 * 1 + 3 * 2 = 8
10) 123|23|54 = 1 * 1 + 2 * 2 = 5
11) 312|23|54 = 0 * 1 + 2 * 2 = 4
12) 231|23|54 = 1 * 1 + 2 * 2 = 5

见题面

见题面