욱제는 준원이랑 끝말잇기를 하고 있다. 준원이가 시작하자마자 '스트론튬'을 외쳐서 욱제는 피가 거꾸로 솟았다\( 솟으면 백두산\) 백두산은 높아\( 높으면 비행기\) 비행기는 빨라\( 빠르면 기차\) 기차에 타고 내릴 때에는 코로나 바이러스 감염증 예방을 위하여 마스크를 착용하여 주시길 당부 드립니다.</p>

준원이와의 끝말잇기 대결에서 패배한 욱제는 새로운 게임을 제안했다. 바로 팰린드롬 문자열만 사용할 수 있는 팰린드롬 끝말잇기이다! 욱제와 준원이는 총 $N$개의 팰린드롬 문자열 $S_1, \cdots, S_N$을 알고 있다. 이 둘이 알고 있는 팰린드롬 문자열을 남김 없이 모두 사용했을 때, 끝말잇기를 할 수 있는지 알아보자. 문자열을 사용하는 순서는 상관 없다.

"리효리", "찰진 의사의 진찰", "탄도유도탄"과 같이 앞으로 읽으나 뒤로 읽으나 똑같은 문자열을 팰린드롬 문자열이라고 부른다. 다시 말해, 길이 $M$짜리 문자열 $T$에 대해, $T[i] = T[M-i+1]$ ($1 \le i \le M$)이면 $T$는 팰린드롬 문자열이다.

$N$개의 팰린드롬 문자열 $P_1, \cdots, P_N$에 대해, $P_i$의 마지막 문자와 $P_{i+1}$의 첫 문자가 같으면 끝말잇기를 할 수 있다고 정의한다. ($1 \le i < N$)

입력 형식

첫째 줄에 문자열의 개수 $N$이 주어진다.</p>

둘째 줄에 $N$개의 팰린드롬 문자열 $S_1, \cdots, S_N$이 하나의 공백을 사이에 두고 주어진다.

출력 형식

주어진 팰린드롬 문자열을 모두 사용했을 때 끝말잇기를 할 수 있으면 1, 그렇지 않다면 0을 출력한다.

예제 입력 1

3
pqqp pqpqp pbbbp

예제 출력 1

1

예제 입력 2

3
aba c dd

예제 출력 2

0