7301번 - ACM-Telecom 다국어

ACM-Telecom provides communication services for international telephone calls. Cost of calling a country (call rates), varies from one to another. The company maintains the rates in a cost table mapping the country codes to call rates. Upon receiving a call, an automatic system determines the country code by looking at the leftmost digits in the 8-digit dialed number and charges the client according to the call rate of that country. More precisely, the automatic system maintains a list of country codes sorted in decreasing order. Upon receiving a call, the system starts from the top of the list and checks if the country code is a prefix of the dialed number. The first country code satisfying this property is considered as the destination of the call and the client is charged according to the call rate of that country. Note that the cost table covers every possible 8-digit number dialed, i.e., every dialed number matches with some country code in the table. Given the relatively high number of rows in the cost table and the increasing number of calls, the computation of call rates has become a quite lengthy process. Your task is to find a new cost table with the minimum number of rows such that the computed call costs for every possible (8-digit) dialed number are the same as before.

The first line of the input contains a single integer t (1 ≤ t ≤ 20) which is the number of test cases in the input. Each test case starts with a line containing a single integer N (1 ≤ N ≤ 1000) which is the number of rows in the cost table. Following the first line, there are N lines of the form code cost where code is an integer between 1 and 9999 clusive, and cost (1 ≤ cost ≤ 100) is a positive integer which is the cost rate of the calls to the country code. There are no two lines with the same country code in a test case.

For each test case, there is one line in the output containing the minimum number of rows of the table required to compute the costs correctly.