SPOJ Brasil

O satebol é um esporte recém-criado por coreanos, russos e brasileiros que está conquistando seus primeiros praticantes e fãs pelo mundo. Para alavancar a popularização desse esporte em Nlogônia, A CNS (Confederação Nlognonense de Satebol) decidiu elaborar o primeiro campeonato nlogonense de satebol. Diversas equipes de satebol foram formadas no país, e irão disputar o campeonato em poucos meses.

A população de Nlognônia está bastante ansiosa para o início do campeonato. Entretanto, ela enfrenta um problema: como o esporte foi récem-criado, as equipes de satebol são muito novas, e nenhum nlognonense decidiu ainda para qual equipe torcer.

Toda pessoa nlognense aceita torcer para qualquer equipe do país, desde que:

• Cada pessoa deve torcer para exatamente uma equipe;
• Se duas pessoas distintas são amigas, então ambas devem necessariamente torcer para a mesma equipe;
• Se duas pessoas distintas não são amigas, então ambas devem necessariamente torcer para equipes diferentes.

Sua tarefa é, considerando o cenário acima, determinar se é possível associar uma equipe para cada pessoa torcer. Em caso positivo, determine o maior número possível de equipes para as quais há pelo menos um torcedor.

Considere que o número de equipes formadas para o campeonato é suficientemente grande, de forma que, se a criação de torcidas é possível, então, para cada pessoa, há garantidamente uma equipe para a qual ela pode torcer.

Entrada

A entrada consiste em vários casos de teste. Cada caso de teste inicia com um inteiro N (1 ≤ N ≤ 10³), indicando a população de Nlognônia. As pessoas nlognenses são numeradas de 1 a N. As próximas N linhas contém N caracteres cada, não separados. O i-ésimo caractere da linha j é 1 se a pessoa i é amiga da pessoa j, e 0 caso contrário. É garantido que o i-ésimo caractere da linha j é igual ao j-ésimo caractere da linha i, e que o i-ésimo caractere da linha i é 0.

O último caso de teste é seguido de uma linha contendo um zero.

Saída

Para cada caso de teste, imprima o maior número possível de equipes para as quais há pelo menos um torcedor. Caso a criação de torcidas não seja possível, imprima impossivel.

Examplo

Entrada:
6
001001
000110
100001
010010
010100
101000
4
0100
1010
0101
0010
0

Saída:
2
impossivel