Person in Charge

• 035966_L3

Attention

The sample cases for this problem are not located in subtask 0. Instead, they are placed elsewhere:

Each sample will be judged three times.

Subtask dependencies are as follows:

File I/O is required (translation.in / translation.out).

Problem Background

In 1922, the Commercial Press in Shanghai published the first Chinese translation of Don Quixote, titled The Magic Knight. Translator Lin Shu, who knew no Western languages, completed this Spanish classic with the help of his friend Chen Jialin, who read an English version aloud to him. Thus Lin Shu half-translated, half-recreated Don Quixote in classical Chinese, condensing the first 55 chapters into four sections.

A century later, Spanish sinologist Alicia Relinque translated this Chinese Don Quixote back into Spanish. The Ingenious Gentleman Don Quixote of La Mancha left 17th-century Spain, sojourned in China as The Magic Knight, and finally returned to Spain—completing a perfect adventure. Last month, the Cervantes Institute launched the Chinese–Spanish edition of The Magic Knight simultaneously in Madrid, Shanghai, and Beijing. The volume contains Lin Shu’s original text alongside Relinque’s Spanish re-translation, enriched with extensive notes and a detailed introduction.

This linguistic odyssey began eight years ago when the Cervantes Institute in Beijing exhibited Chinese translations of Cervantes’ works—collected over twenty years by Chinese bibliophile Liu Ruiming. Among the treasures was the 1934 edition of Lin Shu’s The Magic Knight—“a seemingly ordinary notebook, yet the brightest jewel in the exhibition,” as Imma González Bou, director of the Cervantes Institute in Shanghai, recalled. She initiated the re-translation project, determined to rescue this forgotten Chinese version. Under Relinque’s tireless efforts, the Spanish Magic Knight was born.

Imma sought to see how Lin Shu transformed the protagonist’s original image, thereby revealing how Don Quixote was received in early 20th-century China. Luis García Montero, director of the Cervantes Institute, noted that readers can sense the cultural parallels and contrasts between Spain and China through Don Quixote’s shifting portrayals.

From Spanish to English, English to Chinese, and Chinese back to Spanish, Lin Shu and Relinque’s cross-temporal collaboration allowed Don Quixote to complete a perfect closed loop.

(Source: https://www.jiemian.com/article/6014287.html)

A work can be translated into another language and then translated back? Sleeping Goose was intrigued and decided to start with a single word, exploring the secret of back-translation.

Problem Description

To gather first-hand data, Sleeping Goose interviewed translator Long Long Giraffe and learned the following:

• For a certain meaning X, there are $n$ corresponding words in various languages, where word $i$ belongs to language $c_i$.
• To facilitate translation, Long Long Giraffe arranged semantically similar words consecutively, forming a directed cycle $\ldots \to 1 \to 2 \to \ldots \to n \to 1 \to \ldots$
• Words of the same language that are too similar have been removed, so adjacent words in the cycle never share the same language.
• The semantic deviation between two words $a$ and $b$ is defined as the minimum number of edges that must be traversed along the directed cycle from $a$ to $b$ (not necessarily equal to the reverse direction).
• When translating word $i$ into language $k$ (language $k$ must differ from the language of word $i$), Long Long Giraffe chooses the word $j$ that
  • belongs to language $k$, and
  • minimizes the semantic deviation from $i$ to $j$.

Now Sleeping Goose wants to know: for every word $i$ in the directed cycle, what is the minimum number of translations needed to bring the word back to $i$ itself?

Input Format

Multiple test cases.
First line: an integer $T$, the number of test cases.

For each test case:

• First line: an integer $n$.
• Second line: $n$ positive integers $c_1, c_2, \ldots, c_n$.

Guarantees:

• $n \ge 5$ and $1 \le c_i \le i$.
• Words $1$ and $n$ are not in the same language.
• For $i \ge 2$, words $i$ and $i-1$ are not in the same language.
• If language $i$ does not appear in the input, then language $i+1$ does not appear either.
• For $i \ge 2$, the first occurrence of language $i$ (if any) is strictly later than the first occurrence of language $i-1$.

Output Format

For each test case, output one line of n positive integers: the $k$-th integer is the minimum number of translations required to bring word $k$ back to itself.

Samples

5
5
1 2 1 2 3
5
1 2 1 3 2
5
1 2 3 1 2
5
1 2 3 1 3
5
1 2 3 2 3

2 2 3 4 2
2 3 4 2 2
3 4 2 2 2
4 2 2 2 3
2 2 2 3 4

5
16
1 2 3 4 2 3 4 1 3 1 3 4 2 3 4 2
16
1 2 3 4 3 2 4 1 3 1 3 4 2 3 4 2
16
1 2 3 4 3 4 2 1 3 1 3 4 2 3 4 2
16
1 2 3 4 3 4 1 3 1 3 2 4 2 3 4 2
16
1 2 3 4 3 4 1 3 1 2 3 4 2 3 4 2

4 4 4 4 5 4 5 4 5 6 6 4 4 5 4 5
4 4 4 4 5 5 5 4 5 6 6 4 4 5 4 5
4 4 4 4 5 6 4 4 5 6 6 4 4 5 4 5
3 4 3 3 4 5 4 5 6 6 3 4 5 4 4 4
3 4 3 3 4 5 4 5 6 3 4 4 5 5 5 5

Sample 1 Explanation

For the third test case, the optimal back-translation strategies for the five words are:

1. $\text{Word 1}\xrightarrow{\text{Language 3}}\text{Word 3}\xrightarrow{\text{Language 2}}\text{Word 5}\xrightarrow{\text{Language 1}}\text{Word 1}$
2. $\text{Word 2}\xrightarrow{\text{Language 1}}\text{Word 4}\xrightarrow{\text{Language 2}}\text{Word 5}\xrightarrow{\text{Language 1}}\text{Word 1}\xrightarrow{\text{Language 2}}\text{Word 2}$
3. $\text{Word 3}\xrightarrow{\text{Language 1}}\text{Word 4}\xrightarrow{\text{Language 3}}\text{Word 3}$
4. $\text{Word 4}\xrightarrow{\text{Language 3}}\text{Word 3}\xrightarrow{\text{Language 1}}\text{Word 4}$
5. $\text{Word 5}\xrightarrow{\text{Language 3}}\text{Word 3}\xrightarrow{\text{Language 2}}\text{Word 5}$

Data Range

For $100\%$ of the data: $1 \le T \le 10$, $5 \le n \le 10^5$.

There are four equally-weighted subtasks:

1. $n \le 100$.
2. Each language appears in at most $5$ words.
3. There are at most $5$ distinct languages.
4. No additional constraints.