Alice has a large chandelier at home. A chandelier consists of many light bulbs. Only one light bulb is hung from the ceiling, and the remaining light bulbs are hung from other light bulbs. In other words, the entire chandelier is essentially a tree. The light bulb numbered 1 is hung from the ceiling, and all other light bulbs are hung from a light bulb with a smaller index than their own.

Now, Alice wants to throw a party and wants to renovate this chandelier by changing the light bulbs to different colors. She wants all light bulbs of the same color to be connected, and she wants the number of light bulbs of each color to be the same.

Alice wants you to tell her what the possible schemes are.

Alice is a greedy child. If she finds that there are not enough schemes, or too many, she will be unhappy and will try to adjust the chandelier. For a light bulb with index $x$ ($x \neq 1$), if it was originally hung from the light bulb with index $f[x]$, Alice will re-hang the $x$-th light bulb from the light bulb with index $(f[x] + 19940105) \pmod{x-1} + 1$.

Since "nine" represents a very large number in ancient Chinese, Alice decides to perform this adjustment 9 times. For the initial state and each of the 9 adjusted states, Alice wants you to tell her the possible schemes for each state.

Input

The first line contains an integer $n$, representing the number of light bulbs.

The next line contains $n-1$ integers $U_i$, where the $i$-th number indicates that the $(i+1)$-th light bulb is hung under the $U_i$-th light bulb. It is guaranteed that the light bulb numbered 1 is hung from the ceiling. The numbers are separated by commas ',', and there is no comma after the last number.

Output

For the 10 states, you need to output the results in order.

For each state, you must first output a single line indicating the state number, as shown in the example.

After that, output several lines, each containing one integer, representing the number of light bulbs of each color in a valid partition scheme.

Output these values in ascending order.

Examples

Input 1

6
1,2,3,4,5

Output 1

Case #1:
1
2
3
6
Case #2:
1
2
6
Case #3:
1
3
6
Case #4:
1
3
6
Case #5:
1
3
6
Case #6:
1
2
6
Case #7:
1
2
3
6
Case #8:
1
6
Case #9:
1
2
6
Case #10:
1
3
6

Constraints

For 20% of the data, $n \le 3 \times 10^3$. For 40% of the data, $n \le 5 \times 10^4$. For 50% of the data, $n \le 1 \times 10^5$. For 60% of the data, $n \le 3 \times 10^5$. For 70% of the data, $n \le 7 \times 10^5$. For 100% of the data, $n \le 1.2 \times 10^6$.