В Токио проходит турнир по сумо, в котором участвуют 2^N спортсменов. В каждом поединке обязательно есть победитель, а проигравший выбывает из турнира. Таким образом, чтобы определить победителя турнира, необходимо провести N раундов.

Организаторы хотят, чтобы в как можно большем числе раундов все поединки прошли между сумоистами из разных префектур Японии. Для этого они могут подтасовать результаты жеребьевки произвольным образом.

В первой строке записано число N (1 ≤ N ≤ 10). В каждой из следующих 2^N строк записаны имя сумоиста и префектура, которую он представляет. Имя и префектура являются последовательностями латинских букв длиной не более 30.

Выведите максимальное количество раундов, в которых сумоисты из одной префектуры гарантированно не встретятся (то есть найдите наибольшее возможное число K, такое, что при какой-то начальной расстановке соперников, независимо от исхода поединков, по крайней мере в K раундах все поединки будет сыграны между сумоистами из разных префектур).