COLOR_CC - Colors

no tags 

Given a Bipartite graph with N nodes, you have to colour each node in a way such that no two adjacent nodes have the same colour . Each node is allowed to choose colour from a subset of colours. print the possible number of ways.
You are given a symmetric matrix i.e. matrix[i][j] is always equal to matrix[j][i]
if matrix[i][j]=='Y' then nodes i and j are connected by an edge matrix[i][j]=='N' then nodes i and j are not connected

Input

T -number of test cases ( N test cases follow )

N -number of nodes in graph . N lines corresponding to matrix

N line follows : each line contains xi -- total colours ith node can take , followed by i colours

Output

Print the possible number of ways to colour the graph


T would be less than 20
0<= N <= 13
size of matrix will be N*N
each element of matrix would be either 'Y' or 'N'
number of colours a node can take would be greater then equal to 0 and less than equal to 8 colour number would be less than 100000

Example

Input

1

4

NYNN

YNNN

NNNY

NNYN

3 1 2 3

2 4 5

3 4 5 6

3 1 2 3

 

Output

54


hide comments
Aman Singhal: 2013-03-22 04:21:18

Will graph always be a connected graph ?

Ehor Nechiporenko: 2013-02-19 13:58:29

YEES! My solution was accepted!


Added by:smit hinsu
Date:2013-02-18
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:CodeCraft 13 , Author : Shubhanshu Agarwal