Since Noura Boubou is one of the best photographers in the ACPC, she attends most events, and takes a lot of pictures. Her photos, therefore, are scattered in different unorganized folders in her external hard drive.
During the preparation for SCPC2015, she needed specific photos from her hard drive, so coach Fegla advised her to install a program called "Everything" that works in the following way:
The search tool takes a text as an input, and outputs - in lexicographical order - all the file names that has the entered text as a prefix. Note that the empty string is a prefix of any file name.
Given the names of the files on the hard drive. For each file, find the minimum number of moves needed to find and select the file using this search tool.
Here is the set of the allowed moves: {UP, DOWN, HOME, END, TYPE one letter}.
At the beginning, the focus is on the search box, after typing the needed prefix (zero or more characters), pressing DOWN will select the first result, after that, you can move down or up in the list, pressing END will move you to the last result, and pressing HOME will move you to the first one.
Note that you need to press DOWN at least once (before pressing HOME / END / UP) to move from the search box to the list of results.
For each file, the process starts all over again from the search box.
The first line of input contains an integer T (1 ≤ T ≤ 100), the number of test cases.
The first line of each test case contains an integer N (1 ≤ N ≤ 105), the number of files on the hard drive. Then N lines follow, each line contains the name of one of the files.
For each test case print N space - separated integers on a single line, the ith number is the minimum number of moves needed to find and select the ith file.
Warning: large Input/Output data, be careful with certain languages.
## Input
The first line of input contains an integer T (1 ≤ T ≤ 100), the number of test cases.The first line of each test case contains an integer N (1 ≤ N ≤ 105), the number of files on the hard drive. Then N lines follow, each line contains the name of one of the files. Each file name consists of lowercase English letters only (a-z). No two files have the same name. The length of any file name is at least 1 and at most 105. Total number of characters in one test case doesn’t exceed 5 × 105.
## Output
For each test case print N space - separated integers on a single line, the ith number is the minimum number of moves needed to find and select the ith file.
[samples]
## Note
Warning: large Input/Output data, be careful with certain languages.
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case $ k \in \{1, \dots, T\} $:
- Let $ N_k \in \mathbb{Z} $ denote the number of files.
- Let $ F_k = (f_{k,1}, f_{k,2}, \dots, f_{k,N_k}) $ be the list of file names (strings), ordered lexicographically as stored.
**Constraints**
1. $ 1 \le T \le 100 $
2. For each $ k $: $ 1 \le N_k \le 10^5 $
3. File names are non-empty strings over printable ASCII characters.
**Objective**
For each file $ f_{k,i} $, compute the minimum number of moves to select it, where moves are:
- **TYPE**: one character (each character typed counts as one move)
- **DOWN**: move to next result in list (from search box or any result)
- **UP**: move to previous result
- **HOME**: jump to first result
- **END**: jump to last result
**Key Rules**:
- Search starts with focus on the search box.
- Must press **DOWN at least once** to enter the results list.
- For a file $ f_{k,i} $, choose a prefix $ p $ such that $ p $ is a prefix of $ f_{k,i} $, and $ p $ is not a prefix of any file that comes before $ f_{k,i} $ in lexicographic order unless it is also a prefix of $ f_{k,i} $.
- Let $ S_p $ be the set of files with prefix $ p $, sorted lexicographically. Let $ r $ be the 1-based rank of $ f_{k,i} $ in $ S_p $.
- The number of moves to select $ f_{k,i} $ using prefix $ p $ is:
$$
|p| + 1 + \min(r - 1, |S_p| - r, r - 1 + 1, |S_p| - r + 1)
$$
where:
- $ |p| $: number of TYPE moves
- $ 1 $: mandatory DOWN move
- $ \min(r - 1, |S_p| - r, r - 1 + 1, |S_p| - r + 1) $: minimum of:
- UP/DOWN to reach from first result: $ r - 1 $
- UP/DOWN from last result: $ |S_p| - r $
- HOME + DOWNs: $ 1 + (r - 1) $
- END + UPs: $ 1 + (|S_p| - r) $
**Final Objective**
For each $ i \in \{1, \dots, N_k\} $, compute:
$$
\min_{p \in \mathcal{P}_i} \left( |p| + 1 + \min(r_p(i) - 1, |S_p| - r_p(i), r_p(i), |S_p| - r_p(i) + 1) \right)
$$
where $ \mathcal{P}_i $ is the set of all prefixes of $ f_{k,i} $, and $ r_p(i) $ is the rank of $ f_{k,i} $ among files with prefix $ p $.