COLOR_CC - Colors

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 (T 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.

Constraints

T will be less than 20
0 <= N <= 13, size of matrix will be N * N, and each element of matrix would be either 'Y' or 'N'.
Number of colours a node can take would be greater than 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

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

hide comments
2020-04-10 18:55:26 Scape
For those who are confused what should be the output when N=0, there is no case with N=0

Last edit: 2020-04-10 18:55:57
2013-03-22 04:21:18 Aman Singhal
Will graph always be a connected graph ?
2013-02-19 13:58:29 Ehor Nechiporenko
YEES! My solution was accepted!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.