ACM-Telecom

ACM-Telecom은 국제 전화 통화 서비스를 제공한다. 통화 요금은 국가마다 다르며, 회사는 각 국가 번호(country code)를 통화 요금에 대응시키는 요금표를 관리한다. 전화가 걸려오면 자동 시스템은 8자리로 다이얼된 번호의 가장 왼쪽 숫자들을 보고 국가 번호를 판정하여, 해당 국가의 요금으로 요금을 부과한다.

좀 더 정확히 말하면, 시스템은 국가 번호들을 내림차순으로 정렬한 목록을 유지한다. 전화가 걸려오면 목록의 맨 위에서부터 시작하여, 그 국가 번호가 걸려온 번호의 접두사(prefix)인지 확인한다. 이 조건을 처음으로 만족하는 국가 번호가 통화의 목적지로 간주되고, 그 국가의 요금이 부과된다.

요금표는 가능한 모든 8자리 번호를 포함한다. 즉, 다이얼된 모든 번호는 표의 어떤 국가 번호와 반드시 대응된다.

요금표의 행 수가 많고 통화량도 늘면서 요금 계산 과정이 상당히 오래 걸리게 되었다. 가능한 모든 8자리 번호에 대해 계산되는 통화 비용이 이전과 완전히 동일하도록 유지하면서, 행의 수가 최소인 새로운 요금표를 찾아라.

첫째 줄에 테스트 케이스의 수를 나타내는 정수 $t$ ($1 \le t \le 20$)가 주어진다.

각 테스트 케이스의 첫째 줄에는 요금표의 행 수를 나타내는 정수 $N$ ($1 \le N \le 1000$)이 주어진다. 이어지는 $N$개의 줄에는 각각 code cost 형식으로 한 행이 주어진다. 여기서 code는 $1 \le \text{code} \le 9999$인 정수이고, cost ($1 \le \text{cost} \le 100$)는 그 국가 번호로의 통화 요금을 나타내는 양의 정수이다. 한 테스트 케이스 안에서 같은 국가 번호를 가진 두 줄은 없다.

각 테스트 케이스마다, 비용을 올바르게 계산하기 위해 필요한 표의 최소 행 수를 한 줄에 출력한다.