#include<cmath>

#include<cstdio>

#include<cstring>

using namespace std;

const int mod=1e9+;

char s[];

int broken[];

int bit[];

int f[][];

int ans[];

int main()

{

    int T;

    scanf("%d",&T);

    int n,m;

    int tot;

    while(T--)

    {

        scanf("%d",&n);

        tot=;

        for(int i=;i<=n;++i)

        {

            scanf("%s",s+);

            broken[i]=;

            for(int j=;j<=n;++j)

                if(s[j]=='*') broken[i]|=<<j-;

                else tot<<=,tot-=tot>=mod ? mod : ;

        }

        ans[]=; ans[n+]=tot;

        for(int sz=;sz<=n;++sz)

        {

            memset(f,,sizeof(f));

            f[][]=;

            bit[]=;

            for(int i=;i<n;++i) bit[i]=bit[i-]*sz;

            m=;

            for(int i=;i+sz-<=n;++i) m=m*sz+sz-;

            for(int i=;i<=n;++i)

                for(int st=;st<=m;++st)

                    if(f[i-][st])

                        for(int j=;j<<<n;++j)

                            if(!(broken[i]&j))

                            {

                                int nxt=;

                                for(int tmp=j,l=;l+sz-<=n;++l,tmp>>=)

                                {

                                    int now=(tmp&((<<sz)-))==((<<sz)-) ? st/bit[l-]%sz+ : ;

                                    if(now>=sz) { nxt=-; break; }

                                    nxt+=now*bit[l-];

                                }

                                if(nxt!=-)

                                {

                                    f[i][nxt]+=f[i-][st];

                                    f[i][nxt]-=f[i][nxt]>=mod ? mod : ;

                                }

                            }

            ans[sz]=;

            for(int st=;st<=m;++st)

            {

                ans[sz]+=f[n][st];

                ans[sz]-=ans[sz]>=mod ? mod : ;

            }

        }

        for(int i=;i<=n;++i) printf("%d\n",(ans[i+]-ans[i]+mod)%mod);

    }

    return ;

}

Problem Description

Nothing is more beautiful than square! So, given a grid
of cells, each cell being black or white, it is reasonable to evaluate this
grid’s beautifulness by the side length of its maximum continuous subsquare
which fully consists of white cells.

Now you’re given an N × N grid, and
the cells are all black. You can paint some cells white. But other cells are
broken in the sense that they cannot be paint white. For each integer i between
0 and N inclusive, you want to find the number of different painting schemes
such that the beautifulness is exactly i. Two painting schemes are considered
different if and only if some cells have different colors. Painting nothing is
considered to be a scheme.

For example, N = 3 and
there are 4 broken cells as shouwn in Fig. J(a). There are 2 painting schemes
for i=2 as shown in Fig. J(b) and J(c).

You just need to output the
answer modulo 10⁹ + 7.

 

Input

The first line contains an integer T (T ≤ 10) denoting
the number of the test cases.

For each test case, the first line contains
an integer N (1 ≤ N ≤ 8), denoting the size of the grid is N × N . Then N lines
follow, each line containing an N-character string of “o” and “*”, where “o”
stands for a paintable cell and “*” for a broken cell.

 

Output

For each test case, for each integer i between 0 and N
inclusive, output the answer in a single line.

 

Sample Input

 

Sample Output