Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
ACM-Telecom
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 135Accepted: 16

Description

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.

Input

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 inclusive, 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.

Output

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.

Sample Input

1
12
331 4
33 4
335 4
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9

Sample Output

10

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator