Biased Standings

Usually, results of competitions are based on the scores of participants. However, we are planning a change for the next year of IPSC. During the registration, each team enters a single positive integer, its preferred place in the ranklist. We will take all these preferences into account, and at the end of the competition we will announce a ranklist that pleases as many of you as possible.

But what would that ranklist look like if it is not possible to satisfy all the requests?

Suppose we already have a ranklist. For each team, compute the distance between its preferred place and its place in the ranklist. The sum of these distances is called the badness of the ranklist.

Given team names and their preferred placements, find one ranklist with the minimal possible badness.

The first line of the input contains an integer T, the number of test cases. Each test case is preceded by a blank line.

Each test case has the following form. The first line contains N, the number of teams. Each of the next N lines contains a team name (a string of letters and digits) and its preferred place (an integer between 1 and N, inclusive). No two team names are equal. A team name has at most 20 characters.

For each test case, output a single line with one integer: the badness of the best ranklist for the given teams.

• 1 ≤ T ≤ 20

In the first test case, one possible ranklist with the minimal badness is:

1. noobz
2. llamas
3. Winn3rz
4. 5thwheel
5. NotoricCoders
6. WhoKnows
7. StrangeCase

In the second test case, all ranklists are equally good.