폭탄 받아라

매드 사이언티스트 승혁이는 문기를 곯려주려고 선물로 위장한 폭탄을 준비한다. 정사각형 격자판을 만들어 모든 칸에 잘 폭발하는 원소를 하나씩 넣는데, 같은 원소를 여러 칸에 넣어도 된다.

원소의 종류는 알파벳 소문자 한 개로 나타내므로 최대 26가지를 쓸 수 있다.

문제가 되는 것은 원소를 놓는 순서다. 원소 $x$가 원소 $y$의 바로 왼쪽이나 바로 위에 놓이는 순간 두 원소가 격렬하게 폭발한다는 규칙이 몇 개 주어진다. 선물을 건네기 전에 터지면 안 되니 승혁이는 이런 배치가 한 군데도 없게 격자판을 채워야 한다.

문기는 격자판이 클수록 좋아하지만 정사각형이 아니면 받지 않는다. 규칙을 지키면서 만들 수 있는 정사각형 격자판의 한 변의 최대 길이를 구하자. 1 × 1 격자판에는 인접한 칸이 없으므로 언제나 만들 수 있다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫째 줄에 폭발 규칙의 개수 $n$이 주어진다($0 \le n \le 676$). 이어지는 $n$개의 줄에 규칙이 알파벳 소문자 두 개 $xy$로 주어진다. $x$가 $y$의 바로 왼쪽이나 바로 위에 있으면 폭발한다는 뜻이다. 두 글자는 같을 수도 있다.

각 테스트 케이스마다 만들 수 있는 정사각형 격자판의 한 변의 최대 길이를 한 줄에 출력한다. 한 변이 20 이상인 격자판을 만들 수 있으면 20을 출력한다.