#include #include using namespace std; static const int UP =0; static const int RIGHT =1; static const int DOWN =2; static const int LEFT =3; class Piece{ public : string str; Piece Rot(int n); bool Match(int n,Piece &p); void SetNull(); bool IsNull(); }; // n * 90度回転。 // n =(0 ... 3); Piece Piece::Rot(int n){ Piece result; result.str = str.substr(n)+ str.substr(0,n); return result; } bool Piece::Match(int n,Piece &p){ int trg; int diff; if(p.IsNull() || this->IsNull()) return true; switch(n){ case UP : trg = DOWN; break; case RIGHT : trg = LEFT; break; case DOWN : trg = UP; break; case LEFT : trg = RIGHT; break; } diff = this->str.at(n) - p.str.at(trg); return (diff ==('a'-'A') || diff ==('A'-'a')); } void Piece::SetNull(){ str = ""; } bool Piece::IsNull(){ return (str==""); } int GetAnswer(Piece *p); void GetAnswer(Piece *p,int depth,int &score, bool *use_flag,Piece *ans); int main(void){ int N; Piece p[9]; cin >> N; for(;N>0;N--){ for(int i=0;i<9;i++){ cin >> p[i].str; } cout << GetAnswer(p) << endl; } return 0; } int GetAnswer(Piece *p){ int score=0; bool use_flag[9]; Piece ans[9]; for(int i=0;i<9;i++){ use_flag[i] = false; ans[i].SetNull(); } GetAnswer(p,0,score,use_flag,ans); return score; } // 4->1->2->5->8->7->6->3->0 // 012 // 345 // 678 void GetAnswer(Piece *p,int depth,int &score, bool *use_flag,Piece *ans){ static const int pos_map[9]={4,1,2,5,8,7,6,3,0}; int pos = pos_map[depth]; Piece tmp; if(depth == 0){ for(int i=0;i<9;i++){ ans[pos] = p[i]; use_flag[i] = true; GetAnswer(p,depth+1,score,use_flag,ans); ans[pos].SetNull(); use_flag[i] = false; } }else{ for(int i=0;i<9;i++){ if(use_flag[i]) continue; for(int r=0;r<4;r++){ tmp = p[i].Rot(r); if(pos>=3 && !tmp.Match(UP ,ans[pos-3])) continue; if(pos<6 && !tmp.Match(DOWN,ans[pos+3])) continue; if(pos!= 2 && pos!= 5 && pos!= 8 && !tmp.Match(RIGHT,ans[pos+1])) continue; if(pos!= 0 && pos!= 3 && pos!= 6 && !tmp.Match(LEFT,ans[pos-1])) continue; if(depth==8){ score+=4; }else{ ans[pos] = tmp; use_flag[i] = true; GetAnswer(p,depth+1,score,use_flag,ans); ans[pos].SetNull(); use_flag[i] = false; } } } } }