HZNUOJ

zp打扫卫生

Tags:
Time Limit:  1 s      Memory Limit:   128 MB
Submission:577     AC:240     Score:86.61

Description

最近,有很多学妹问zp解题方法。zry很吃醋,但认为让zp写检讨书太土了。于是,他想出一招,惩罚zp打扫卫生。他需要打扫在n*n格子的面积,每个格子是干净或者肮脏。

注意:

1. 干净的格子被zp打扫后会变脏,原因要问zp。脏的格子被打扫过之后会变干净;
2. zp挥动一次扫把,就能打扫整一列的格子,但不能是一列中的一部分;
3. zp体力无限,可以挥动扫把无限次。
zry有洁癖,想知道打扫后,怎么让干净的行数(一行全是干净的格子)最多。zp很爱zry,每次都拼命的计算。

Input

第一行输入一个T,代表有T组测试数据;
每组测试数据第一行数据输入一个n(0<n<=100),接下来输入n行n列格子的卫生情况,1代表干净,0代表脏。

Output

打扫后最多干净的格子的行数。

Samples

input
2 4 0101 1000 1111 0101 3 111 111 111
output
2 3

Hint

样例一:zp打扫1,3列之后变成
1111
0010
0101
1111

所以有两行干净 

样例二:不需要打扫则有3行干净


Author

LIN, Ouya

Source

杭州师范大学第九届程序设计竞赛