Description

反映科学研究水平的影响力因素一直都用发表论文的数量和质量来衡量。而引用因子则是一篇论文被其他论文引用的次数，通常拿来评判一篇论文的重要程度。然而，现实中不定因素太多，仅用引用因子是不够的，于是升级为H引用因子。H引用因子显然基于引用因子，对论文质量作出了更准确的评判。

所谓H引用因子，是对于某个人所发表的论文来说，有一个最大整数值H，其有H篇论文，被至少H次引用。也就是说，一个学者的论文具有H引用因子，则其至少发表过H篇论文，每篇都被引用过H次，并且该学者没有H+1篇论文，它们都被引用H+1次。当然，关于引用的问题，如果一篇论文被自己的其他论文引用多少次，也算引用多少次。

如果H引用因子达到18，那就是教授级水平了，H引用因子达到45或更高，就可以成为美国科学院的院士了。你的任务是对所有学者展开H引用因子调查，看看他们的科研水平如何。

Input

若干组数据，每组数据以一个整数N（1≤N≤100）开头，若N为0，则计算结束。N后跟N篇论文，论文以发表者名字表示（长度≤20）。如果一个人发表多篇论文，则人名可能重复。在N篇论文之后是一个N*N的01矩阵，其第i行第j列若为1，表示第i篇论文引用了第j篇论文。

Output

对每组数据列出H引用因子计算结果。即输出每个人的H引用因子。每行一个人名，一个空格，一个H引用因子。先按H引用因子从大到小排列，若H引用因子相同，则按名字的字典序排列。组与组之间空一行。

Sample

Input

4
Peter
Peter
Bob
Bob
0000
1000
1100
0100
0

Output

Peter 2
Bob 0