폭탄 받아라
시간 제한2초메모리 제한128 MB
26개 문자 사이의 금지된 인접 규칙 아래에서 채울 수 있는 가장 큰 정사각형 격자의 한 변 길이를 20을 상한으로 구합니다.
문제
매드 사이언티스트 승혁이는 문기를 곯려주려고 선물로 위장한 폭탄을 준비한다. 정사각형 격자판을 만들어 모든 칸에 잘 폭발하는 원소를 하나씩 넣는데, 같은 원소를 여러 칸에 넣어도 된다.
원소의 종류는 알파벳 소문자 한 개로 나타내므로 최대 26가지를 쓸 수 있다.
문제가 되는 것은 원소를 놓는 순서다. 원소 가 원소 의 바로 왼쪽이나 바로 위에 놓이는 순간 두 원소가 격렬하게 폭발한다는 규칙이 몇 개 주어진다. 선물을 건네기 전에 터지면 안 되니 승혁이는 이런 배치가 한 군데도 없게 격자판을 채워야 한다.
문기는 격자판이 클수록 좋아하지만 정사각형이 아니면 받지 않는다. 규칙을 지키면서 만들 수 있는 정사각형 격자판의 한 변의 최대 길이를 구하자. 1 × 1 격자판에는 인접한 칸이 없으므로 언제나 만들 수 있다.
입력
첫째 줄에 테스트 케이스의 개수 가 주어진다.
각 테스트 케이스의 첫째 줄에 폭발 규칙의 개수 이 주어진다(). 이어지는 개의 줄에 규칙이 알파벳 소문자 두 개 로 주어진다. 가 의 바로 왼쪽이나 바로 위에 있으면 폭발한다는 뜻이다. 두 글자는 같을 수도 있다.
출력
각 테스트 케이스마다 만들 수 있는 정사각형 격자판의 한 변의 최대 길이를 한 줄에 출력한다. 한 변이 20 이상인 격자판을 만들 수 있으면 20을 출력한다.