Twibet (Large)

The holy country of Twibet has $N$ monks. Each monk carries a distinct number from $1$ to $N$, and for religious reasons they use no names. The monks walk slowly around Twibet, and each monk follows exactly one other monk.

Most of the time every monk is silent. On day $K$, monk $K$ stops, turns around and whispers the 140 Words of Wisdom. The whisper is quiet, so only the monks who follow him directly can hear it. Each of those followers then stops, turns around and whispers the same words to his own followers. The chain keeps going. Every monk who has just heard the Words today, and has not whispered them yet today, stops and whispers to his followers.

Once every monk who could hear the Words has whispered them, they all turn back and walk on as usual. The next day the same thing happens again, this time starting from a different monk.

For each $K$ from $1$ to $N$, how many monks whisper the 140 Words of Wisdom on day $K$?

The first line contains the number of test cases $T$.

Each test case starts with a line containing one integer $N$. The next line contains $N$ space-separated integers $F_1, F_2, \dots, F_N$. Monk $i$ follows monk $F_i$.

Constraints

• $1 \le T \le 100$
• $2 \le N \le 1000$
• $1 \le F_i \le N$ and $F_i \ne i$, so no monk directly follows himself.

For each test case, first print one line Case #x:, where $x$ is the test case number starting from $1$.

Then print $N$ lines, one per day. The first of those lines contains the number of monks who whisper the Words on day $1$, the next line the number for day $2$, and so on through day $N$.

In the first test case of the example, all 3 monks walk in a circle. Whoever whispers first, his follower whispers next and the remaining monk whispers after that. So on each of the 3 days all 3 monks whisper.

In the second test case, monk 1 follows monk 2, monk 2 follows monk 3, monk 3 follows monk 2, and monk 4 follows monk 1. On day 1 monk 1 whispers first and monk 4 hears him and whispers next, while monks 2 and 3 hear nothing that day. On day 2 monk 2 whispers first, monks 1 and 3 hear him and whisper next, and monk 4 hears monk 1 and whispers last. On day 3 the monks whisper in the order 3, 2, 1, 4. On day 4 monk 4 whispers and nobody hears him.