C++ :

/*
 *=====================
 *File Name:a.cpp
 *Author: qqspeed
 *Date: 2014年 07月 17日 星期四 11:18:22 CST
 *=====================
 */
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <vector>
#include <stdlib.h>
#include <algorithm>
using namespace std;

typedef long long ll;
#define rep(i,s,t) for(int i=s;i<t;i++)
#define red(i,s,t) for(int i=s-1;i>=t;i--)
#define ree(i,now) for(int i=head[now];i!=-1;i=edge[i].next)
#define clr(a,v) memset(a,v,sizeof a)
#define L t<<1
#define R t<<1|1
#define MID int mid=(l+r)>>1
#define max(a,b) (a<b?b:a)
#define min(a,b) (a<b?a:b)
#define SQR(a) ((a)*(a))

inline int input(){
	int ret=0;bool isN=0;char c=getchar();
	while(c<'0' || c>'9'){
		if(c=='-') isN=1;
		c=getchar();
	}
	while(c>='0' && c<='9'){
		ret=ret*10+c-'0';
		c=getchar();
	}
	return isN?-ret:ret;
}

inline void output(int x){    
    if(x<0){    
        putchar('-');x=-x;    
    }    
    int len=0,data[11];    
    while(x){    
        data[len++]=x%10;x/=10;    
    }    
    if(!len)    data[len++]=0;    
    while(len--)   
        putchar(data[len]+48);    
    putchar('\n');  
}  

int t,n,m,k;
char s[110][110];
int a[110][110];
int dp[110][110][15];

bool in(int x,int y){
	return x>=1 && x<=n && y>=1 && y<=m;
}

int main(){
	//freopen("1","w",stdout);
	t=input();
	while(t--){
		n=input(),m=input(),k=input();
		k++;
		rep(i,0,n) scanf("%s",s[i]);
		rep(i,1,n+1) rep(j,1,m+1){
			a[i][j]=s[i-1][j-1]-'0';
		}
		clr(dp,-1);
		rep(i,1,m+1){
			dp[n][i][a[n][i]%k]=a[n][i];
		}
		red(i,n,1){
			rep(j,1,m+1){
				rep(r,0,k){
					int x=i+1,y=j-1;
					if(in(x,y) && dp[x][y][r]!=-1){
						int nxt=(r+a[i][j])%k;
						int val=dp[x][y][r]+a[i][j];
						if(dp[i][j][nxt]==-1 || dp[i][j][nxt]<val){
							dp[i][j][nxt]=val;
						}
					}
					y=j+1;
					if(in(x,y) && dp[x][y][r]!=-1){
						int nxt=(r+a[i][j])%k;
						int val=dp[x][y][r]+a[i][j];
						if(dp[i][j][nxt]==-1 || dp[i][j][nxt]<val){
							dp[i][j][nxt]=val;
						}
					}
				}
			}
		}
		vector<char>v;
		int id,Max=-1;
		rep(i,1,m+1){
			if(dp[1][i][0]!=-1){
				if(Max<dp[1][i][0]){
					id=i;Max=dp[1][i][0];
				}
			}
		}
		if(Max==-1){
			puts("-1");
		}
		else{
			printf("%d\n",Max);
		/*	rep(i,2,n+1){
				int x=id+1;
				if(in(i,x)){
					int r=(Max-a[i-1][id])%k;
					if(dp[i][x][r]==Max-a[i-1][id]){
						v.push_back('L');
						Max-=a[i-1][id];
						id=x;
						continue;
					}
				}
				x=id-1;
				if(in(i,x)){
					int r=(Max-a[i-1][id])%k;
					if(dp[i][x][r]==Max-a[i-1][id]){
						v.push_back('R');
						Max-=a[i-1][id];
						id=x;
						continue;
					}
				}
			}	
			printf("%d\n",id);
			int S=v.size();
			red(i,S,0){
				printf("%c",v[i]);
			}
			puts("");*/
		}
	}
	return 0;
}