Guilty Rahman

OC Rahman is notorious for accepting bribes. Influential people in his area now seek to bribe him to handle their issues. Despite OC Rahman's recent commitment to improving his behavior by reducing bribery and unethical actions.

Suppose there are $n$ days and $p$ powerful individuals. For each of the $n$ days, OC Rahman gets a new offer from every $p$ powerful individual. OC Rahman starts taking bribes from the first day.

He can complete task of any person $j \:(1\le j\le p)$on any day $i\:(1\le i\le n).$On the $i’th$ day, the $j’th$ person offers OC Rahman a certain amount of money represented by $a[i][j].$ If OC Rahman completes the task assigned by a person on that day, he receives the corresponding amount. However, if OC Rahman completes the task for the $j’th$ person on the $i’th$ day, on the next $(i+1)’th$ day, all individuals except for the $j’th$ person will offer an additional amount of money, denoted by $C$ in addition to their initial offer. No additional money will be applied for any tasks assigned on the first day. Please note that OC Rahman will exactly complete one task per day.

OC Rahman, having reliable sources, gathers information about the daily offers he will receive from each person, as well as the additional amount they will offer. Assist OC Rahman in minimizing the bribes he accepts.

Input

The first line will be a single integer $t(1\le t\le100)$ indicating the number of test cases. For each test case the first line will contain three integers separated by space $n,p(1\le n,p\le 100), C(1\le C\le10^9)$ indicating the number of days and the number of power full people and the number of extra amounts.

Following $n$ lines each line containing $p$ integers $a_{ij}(1\le a_{ij}\le 10^9)$ each indicating the amount offered on the $i’th$ day  by the $j’th$ person.

Output

$t$ lines each line representing OC Rahman’s minimum bribe collection.

Sample

Input	Output
3 2 2 100 1 3 7 1 3 2 2 1 7 7 1 1 5 3 3 2 1 7 7 2 1 5 1 6 6	4 7 4