MATCH - Perfect Matching

no tags 

You are given a bipartite graph with N (1 <= N <= 300) nodes on each side. Determine whether the number of perfect matching is odd or even.

Input

First line is an integer T(1<=T<=20) means the number of test cases. The following are T parts. Each part begin with an integer N(1<=N<=300) means the number of nodes on both sides. It followed with N lines, each line contains a 0/1 string. If the j th (1 <= j <= N) character of the i th (1 <= i <= N) line is 1, it means the i th node on left have an edge to the j th node on right. See the sample for details.

Output

T lines, each contain "Odd" or "Even", which means the parity of the number of the perfect matching. See the sample for details.

Example

Input:
2
1
1
4
1100
1100
0011
0011

Output: Odd
Even

Constraints

1 <= N <= 300
1 <= T <= 20


hide comments
prof_hadi: 2020-03-26 07:47:52

test 15 is my problem too :(

Last edit: 2020-03-26 14:55:29
nsitsk: 2016-03-20 18:21:16

Getting WA on the 15th test case. Please help... :(

adijimmy: 2014-07-17 12:04:27

TLEing on 15th :(

Sanjeev Kumar: 2014-07-17 00:09:23

WA on 15th TC :(

Ravi Ranjan Pandey: 2013-07-19 07:28:58

@ Kunal Jain ,why are i geting WA in 15 test cases :( plzzz help


Added by:Kunal Jain
Date:2011-02-07
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:CodeCraft 11