MATCH - Perfect Matching

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


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

hide comments
2020-03-26 07:47:52
test 15 is my problem too :(

Last edit: 2020-03-26 14:55:29
2016-03-20 18:21:16
Getting WA on the 15th test case. Please help... :(
2014-07-17 12:04:27 adijimmy
TLEing on 15th :(
2014-07-17 00:09:23 Sanjeev Kumar
WA on 15th TC :(
2013-07-19 07:28:58 Ravi Ranjan Pandey
@ Kunal Jain ,why are i geting WA in 15 test cases :( plzzz help
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.