题目描述

都玩过植物大战僵尸吧 。 但是，这次僵尸来进攻时，这些格子里放的不是植物，而是脑子。僵尸不敢独吞，而是想把脑子收集回去给他的K个朋友一起分享，为了不引发各种麻烦，因此他收集的脑子是$\red{K+1}$的倍数。 假设僵尸在地图的下方，而他的家在地图上方，另外，这只僵尸不喜欢走直线，喜欢走斜线，因此他每次只会往左上角走或者往右上角走，每走到一个格子会把这个格子的所有脑子都收集起来，问，怎么走收集的脑子个数最多？他可以在最下方任意选择一个格子作为起点。

输入格式

第一行输入一个数$\red{T}$，表示测试数据个数，对于每组测试数据，第一行输入三个数$\red{n,m,k}$，$\red{n}$和$\red{m}$表示这个地图的大小，$\red{(0<n,m≤100)}$，k表示他有k个朋友。(0≤k≤10)，之后有$\red{n}$行，每行$\red{m}$个数，表示每个格子的脑子个数，每个数都在0到9之间，包括0和9，注意，这些数之间没有空格。

输出格式

对于每组测试数据，输出一个数，表示最多能收集多少个脑，如果没有走法符合条件，输出一个数$\red{-1}$。

样例

输入数据#1

3
3 3 0
123
456
789
3 3 1
123
456
789
2 2 10
98
75

输出数据#1

17
16
-1