403231: GYM101086 C Everything

C. Everythingtime limit per test10 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

For example, we can find and select the file "scpc" in two moves as follows (check the pictures):

• The first window shows that all files are displayed because the search box is empty.
• The second window shows that after typing the letter 's', all files with prefix "s" are displayed.
• The third window shows that after pressing DOWN the first item is selected and in this example it's the file we want.

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 ≤ 10⁵), 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 10⁵.
• Total number of characters in one test case doesn’t exceed 5 × 10⁵.

Output

For each test case print N space - separated integers on a single line, the i^th number is the minimum number of moves needed to find and select the i^th file.

ExamplesInput

2
5
scpc
acm
syria
acpc
accepted
5
feglathegreat
candidatesamerraed
masterhossamyousef
candidateabdullahbahosain
masterhassanalhamsh

Output

2 2 2 3 1
2 2 2 1 2

Note

Warning: large Input/Output data, be careful with certain languages.