#include <bits/stdc++.h>

const int MX = 1000;

char a[MX + 1], b[MX + 1], c[MX + 1];

void calc(char* s, int& count, int &suff) {
	count = 0;
	suff = 0;
	for (int i = 0; s[i] != 0; i++) {
		if (s[i] == '0') suff = 0;
		else {
			count++;
			suff++;
		}
	}
}

int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		int n;
		scanf(" %s %s %s %d", a, b, c, &n);
		
		int ac, as, bc, bs, cc, cs;
		calc(a, ac, as);
		calc(b, bc, bs);
		calc(c, cc, cs);
		
		int ans = ac + bc * n + cc;
		if (cs == 0) ans++;
		else if (cs < strlen(c)) ans -= cs - 1;
		else if (bs < strlen(b)) ans -= cs + bs - 1;
		else ans -= cs + n * bs + as - 1;
		
		printf("%d\n", ans);
	}
	
	return 0;
}