Flip five

#include<iostream>
#include<algorithm>

using namespace std;

int indexArr(int *arr)
{
    int id=0;
    for (int i=0;i<9;i++)
        if (arr[i]==1)
        {
            id+=(1<<(i));
        }
    return id;
}

int *ArrIndex(int id)
{
    int *arr = new int[9];
    for (int i=0;i<9;i++)
    {
        arr[i] = id%2;
        id = id/2;
    }
    return arr;
}

int d2s(int x, int y)
{
    int du[3] = {3,1,2};
    return (x-1)*3+du[y%3];
}

// numMove count on 1;
int *Move(int *arr, int numMove)
{
    int x[10] = {0,1,1,1,2,2,2,3,3,3};
    int y[10] = {0,1,2,3,1,2,3,1,2,3};
    int *arr2 = new int[9];
    for (int i=0; i<9;i++)
        arr2[i]=arr[i];
    arr2[numMove-1] = 1-arr2[numMove-1];
    if (x[numMove]-1>0)
    {
        int tp = d2s(x[numMove]-1,y[numMove]);
        arr2[tp-1] = 1 - arr2[tp-1];
    }
    if (x[numMove]+1<4)
    {
        int tp = d2s(x[numMove]+1,y[numMove]);
        arr2[tp-1] = 1 - arr2[tp-1];
    }
    if (y[numMove]-1>0)
    {
        int tp = d2s(x[numMove],y[numMove]-1);
        arr2[tp-1] = 1 - arr2[tp-1];
    }
    if (y[numMove]+1<4)
    {
        int tp = d2s(x[numMove],y[numMove]+1);
        arr2[tp-1] = 1 - arr2[tp-1];
    }
    return arr2;
}

int BFS(int *arr)
{
    int mark[513]={};
    int queue[513]={};
    int depth[513]={};
    int id = indexArr(arr);
    if (id==0)
        return 0;
    queue[0]= id;
    depth[0]= 0;
    mark[id]=1;
    int start=0, end=1;
    while (start<end)
    {
        int *arr2 = ArrIndex(queue[start]);
        for (int i=1;i<=9;i++)
        {
            int newID = indexArr(Move(arr2,i));
            if (newID==0)
            {
                return depth[start]+1;
            }
            if (mark[newID]==0)
            {
                queue[end]=newID;
                depth[end]=depth[start]+1;
                mark[newID]=1;
                end++;
            }
        }
        delete(arr2);
        start++;
    }
}

void FlipFive()
{
    int arr[9]={};

    for (int i=0;i<9;i++)
    {
        char c = getchar();
        if (c=='*')
            arr[i]=1;
        else if (c=='\n')
        {
            i--;
        }
    }
    cout << BFS(arr);
}

int main()
{
    int n;
    cin >> n;
    char c = getchar();
    for (int i=0;i<n;i++)
    {
        FlipFive();
    }
    return 0;
}