ACM-Telecom

Time limit1sMemory limit128 MB

Summary

Given a prefix table that assigns costs to 8-digit numbers, find the minimum number of prefix rows preserving every number's charged cost.

Level: Medium7 of 10
Topics: Trie, Greedy
Solved: No attempts yet

Problem

ACM-Telecom provides international phone-call services. The call rate differs from country to country, and the company keeps a cost table that maps each country code to a call rate. When a call arrives, an automatic system looks at the leftmost digits of the 8-digit dialed number to determine the country code, and charges the caller at that country's rate.

More precisely, the system keeps the list of country codes sorted in decreasing order. When a call arrives, it starts from the top of the list and checks whether the country code is a prefix of the dialed number. The first country code that satisfies this is taken as the destination of the call, and its rate is charged.

The cost table covers every possible 8-digit number; that is, every dialed number matches some country code in the table.

Because the table has many rows and the number of calls keeps growing, computing call costs has become quite slow. Find a new cost table with the minimum number of rows such that the computed cost of every possible 8-digit dialed number stays exactly the same as before.

Input

The first line contains a single integer $t$ ( $1 \le t \le 20$ ), the number of test cases.

Each test case begins with a line containing a single integer $N$ ( $1 \le N \le 1000$ ), the number of rows in the cost table. The next $N$ lines each have the form code cost, where code is an integer with $1 \le \text{code} \le 9999$ and cost ( $1 \le \text{cost} \le 100$ ) is a positive integer, the call rate for that country code. No two lines in one test case share the same country code.

Output

For each test case, print on one line the minimum number of rows the table needs to compute the costs correctly.

Examples4

Example 1

Input

Expected output

Example 2
Input
```
1
1
1 7
```
Expected output
```
1
```
Example 3
Input
```
1
4
1 5
12 5
123 5
1234 5
```
Expected output
```
1
```
Example 4
Input
```
1
2
5 5
53 6
```
Expected output
```
2
```