该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

负责人

• 035966_L3

注意

本题的样例没有放在子任务 0 中，而是放在了其他地方：

两个样例均会被评测三次。

本题的子任务依赖关系如下：

本题需要使用文件读写（translation.in / translation.out）。

题目背景

1922 年，上海商务印书馆出版了《堂吉诃德》的首个中文译本《魔侠传》。不了解任何西方语言的译者林纾在好友陈家麟口述翻译的帮助下，完成了这部西语文学经典的中文翻译工作。陈家麟读的是英译本，因此林纾半是转译、半是创作，在重重错误间以文言文「重写」了《堂吉诃德》，而且他只「重写」了上半部的内容，把讲述堂吉诃德两次出走的前 55 章整合为四段。

2021 年，西班牙汉学家阿莉西亚·雷林克将这部中文版《堂吉诃德》重新译回西班牙语，《奇思异想的绅士堂吉诃德·德·拉曼却》（原书全名）从 17 世纪的西班牙出走，又以《魔侠传》的面貌自中国归返西班牙，完成了一次圆满的冒险之旅。日前，塞万提斯学院在马德里、上海和北京三地同时发布了汉西版《魔侠传》。该版本包含了林纾原著以及雷林克的西班牙语译本，并附有大量译者注释和详细导读。

从西班牙语到英语，从英语到中文，再从中文回到西班牙语，在林纾和雷林克跨时空的合作下，堂吉诃德走完了一个圆满的闭环。

（资料来源：https://www.jiemian.com/article/6014287.html）

一本著作竟然可以先翻译到其他语言再翻译回来？这引起了 Sleeping Goose 极大的兴趣。它决定先从一个单词开始，探寻「回译」的秘密。

题目描述

为了获得一手数据，Sleeping Goose 采访了翻译家 Long Long Giraffe，并从它口中得知了以下信息：

• 某个义项 X 在各种语言中共有 $n$ 个对应的单词，其中第 $i$ 个单词属于语言 $c_i$。
• 为了方便翻译，Long Long Giraffe 将语义差别较小的单词排在一起，形成了一个 $\ldots \to 1 \to 2 \to \ldots \to n \to 1 \to \ldots$ 的有向环。
• Long Long Giraffe 已经预先剔除了同一种语言中语义差别过小的单词，因此它保证有向环中相邻两个单词一定不属于同一种语言。
• 有向环上 $a \to b$ 经过的最小边数被定义为单词 $a$ 和单词 $b$ 之间的语义偏差度 —— 由于翻译家并不像 OI 选手那样具备逆向思维，因此单词 $a$ 和单词 $b$ 之间的语义偏差度不一定等于单词 $b$ 和单词 $a$ 之间的语义偏差度。
• 根据翻译原则，当 Long Long Giraffe 需要将单词 $i$ 翻译到语言 $k$（语言 $k$ 不能是单词 $i$ 所属的语言）时，它会将单词 $i$ 翻译为使得单词 $i$ 和单词 $j$ 之间的语义偏差度最小且属于语言 $k$ 的单词 $j$。

现在，Sleeping Goose 想要知道：对于有向环中的每一个单词 $i$，Long Long Giraffe 至少要翻译多少次才都能将它翻译回单词 $i$ 呢？

输入格式

本题有多组数据。

第一行输入一个整数 $T$，表示测试数据的数量。

对于每组测试数据：

第一行一个正整数 $n$。

第二行 $n$ 个正整数 $c_1 \sim c_n$。

数据保证：

• $n \ge 5$ 且 $1 \le c_i \le i$。
• 单词 $1$ 和单词 $n$ 不属于同一种语言。
• 对于 $i \ge 2$，单词 $i$ 和单词 $i-1$ 不属于同一种语言。
• 如果语言 $i$ 在输入中没有出现，那么语言 $i+1$ 也不会在输入中出现。
• 对于 $i \ge 2$，语言 $i$ 在输入中第一次出现的位置（如果它出现了）一定晚于语言 $i-1$。

输出格式

对于每组数据，输出一行 $n$ 个正整数，其中第 $i$ 个正整数表示将单词 $i$ 翻译回它翻译回单词 $i$ 所需的最小翻译次数。

样例

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

样例 1 解释

对于第三组数据，$5$ 个单词对应的最优回译策略如下：

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}$

数据范围

对于 $100\%$ 的数据，$1 \le T \le 10$，$5 \le n \le 10^5$。

本题共有四个等分的子任务，各子任务的特殊限制如下：

1. $n \le 100$。
2. 保证每种语言的单词不超过 $5$ 个。
3. 保证语言不超过 $5$ 种。
4. 无特殊限制。