#include <iostream>#include <stdio.h>#include <string.h>#include <algorithm>#include <stdlib.h>using namespace std;int dp[210][210][210];int dat[210][3];char str[210];int a,b,c;int val(int x,int y,int z){ int t = 0; if(x == 0) t++;if(y == 0) t++;if(z == 0) t++; if(t >= 2) return 0; if(x == y && x == z) return 3; if(x == y && z == 0) return 1; if(x == z && y == 0) return 1; if(y == z && x == 0) return 1; return 0;}int dfs(int aa,int bb,int cc){ if(!(aa == a-1 && bb == b-1 && cc == c-1) ) if(aa >= a-1 && bb >= b-1 && cc >= c-1) return 0; if(aa >= a || bb >= b || cc >= c) return -222000; if(dp[aa][bb][cc] != -1) return dp[aa][bb][cc]; dp[aa][bb][cc] = -222000; if(dat[aa][0] == 0) dp[aa][bb][cc] = max(dp[aa][bb][cc], dfs(aa+1,bb,cc)); if(dat[bb][1] == 0) dp[aa][bb][cc] = max(dp[aa][bb][cc], dfs(aa,bb+1,cc)); if(dat[cc][2] == 0) dp[aa][bb][cc] = max(dp[aa][bb][cc], dfs(aa,bb,cc+1)); dp[aa][bb][cc] = max(dp[aa][bb][cc], dfs(aa+1,bb+1,cc+1) + val(dat[aa][0],dat[bb][1],dat[cc][2])); return dp[aa][bb][cc];}int main(){ int t; cin >> t; while(t--) { memset(dat,0,sizeof(dat)); int len; scanf("%s",str);len = strlen(str); a = len*2+1;for(int i = 0;i < len;i++) dat[i*2+1][0] = str[i] -'A' + 1; scanf("%s",str);len = strlen(str); b = len*2+1;for(int i = 0;i < len;i++) dat[i*2+1][1] = str[i] -'A' + 1; scanf("%s",str);len = strlen(str); c = len*2+1;for(int i = 0;i < len;i++) dat[i*2+1][2] = str[i] -'A' + 1; memset(dp,-1,sizeof(dp)); dfs(0,0,0); if(dp[0][0][0] < 0) dp[0][0][0] = -1; cout << dp[0][0][0] << "n"; } return 0;}
