#include<iostream>#include<cstdio>#include<cstring>#include<queue>using namespace std;typedef struct{ int data; int step;}State;queue<State> q;int vis[65536];int dx[] = {-1, 0, 1, 0};int dy[] = { 0, -1, 0, 1};State begin, end;char s[4][4]; int isright(int x, int y){ if(x < 0 || x > 3 || y < 0 || y > 3) return 0; return 1;}int main(){ int ncases, i, j, bstate, ok, k, x, y, nx, ny; scanf("%d", &ncases); while(ncases--) { bstate = 0; memset(vis, 0, sizeof(vis)); for(i = 0; i < 4; i++) { scanf("%s", s[i]); for(j = 0; j < 4; j++) { if(s[i][j] == 'b') { bstate |= 1 << (i*4+j); } } } ok = 0; begin.data = bstate; begin.step = 0; vis[begin.data] = 1; q.push(begin); while(!q.empty()) { State u = q.front(); q.pop(); if(u.data == 0 || u.data == 65535) { ok = 1; printf("%dn", u.step); break; } for(k = 0; k < 16; k++) { State v; v.step = u.step + 1; v.data = u.data ^ (1 << k); x = k / 4; y = k % 4; for(i = 0; i < 4; i++) { nx = x + dx[i]; ny = y + dy[i]; if(isright(nx, ny)) { v.data = v.data ^ (1 << (nx*4+ny)); } } if(!vis[v.data]) { q.push(v); vis[v.data] = 1; } } } if(!ok) { printf("Impossiblen"); } if(ncases) putchar(10); while(!q.empty()) q.pop(); } return 0;}
