A sumo tournament is held in Tokyo, in which 2^{N} sportsmen take part.
In each encounter there is a winner, and the loser drops out of the tournament.
Thus, in order to determine the winner of the tournament, it is necessary to
conduct N rounds.
The organizers wish that in as many rounds as possible all encounters
would be held between sumoists from different prefectures of Japan.
For that they can forge the drawing results arbitrarily.
Input
The first line contains the number N (1 ≤ N ≤ 10).
Each of the next 2^{N} lines contains the name of a sumouist and
the prefecture which he presents. The name and prefecture are sequences of
Latin letters of length not exceeding 30.
Output
Output the maximal number of rounds in which sumoists from the same prefecture
will not fight each other regardless of the outcomes of encounters (that is,
find the maximal possible K such that in at least K rounds all encounters
will be between sumoists from different prefectures). The organizers can control
the initial arrangement of sportsmen but can't control results of encounters.
Sample
input  output 

3
Homasho Ishikawa
Tamakasuga Tokyo
Futeno Tochigi
Takekaze Tokyo
Kasugao Yamaguchi
Kotoshogiku Ishikawa
Kotomitsuki Tokyo
Miyabiyama Shizuoka
 1

Problem Author: Sergey Pupyrev
Problem Source: The 11th Urals Collegiate Programing Championship, Ekaterinburg, April 21, 2007