友情提示：380元/半年，儿童学编程，就上码丁实验室。
【题目描述】
桌子上有 $n$ 个石头围成一个环。每个石头都有一种颜色。每种颜色可以用不同的小写英文字母表示，所以总共有$26$种颜色。不同的石头可能有相同的颜色。如果每一对相邻的石头都是不同颜色的，则称这$n$个石头构成的环是美丽的。两个石头是相邻的充要条件是这两个石头中间没有其他石头。例如：$1$号和 $2$号是相邻的，$2$号和$3$号是相邻的，…，$n$号和$1$号是相邻的。现在，你可以从这 $n$ 个石头中拿走一段连续的石头（可以为空），且你只能拿一次。你的任务是对于每个$k(0≤k≤n-1)$，判断是否存在一种取石头的方案，使得在拿走$k$个连续的石头后，剩下的$n-k$个石头构成的环是美丽的。
【输入】
输入包含多组测试数据，以$EOF$结束。
每组数据有一行字符串$s$，字符串第$i$位表示桌上第$i$个石头的颜色。设字符串$s$的长度为$n$，则$1≤n≤10^6$。字符串只包含小写英文字母。
【输出】
对于每组数据，按照样例的格式输出数据编号和一个长度为$n$的字符串。如果存在一种取石头的方案，使得在拿走$k$个连续的石头后，剩下的$n-k$个石头构成的环是美丽的，则字符串的第$k$位（由$0$开始编号）为$1$，否则为$0$。
【输入样例】
rrg rrrrr brbg abab
【输出样例】
Case 1: 011 Case 2: 00001 Case 3: 1111 Case 4: 1011
【提示】
【数据规模】
对于所有数据，数据组数不超过 $6$ 组，$1≤n≤10^6$。
| 测试点编号 | $n$ | 特殊限制 |
| $1$ | $≤1000$ | |
| $2$ | ||
| $3$ | $≤10^5$ | 输入的$n$个石子中，任意两个相邻的石子颜色不同。 |
| $4$ | ||
| $5$ | ||
| $6$ | ||
| $7$ | ||
| $8$ | ||
| $9$ | ||
| $10$ | ||
| $11$ | $≤10^6$ | 输入的$n$个石子中，任意两个相邻的石子颜色不同。 |
| $12$ | ||
| $13$ | ||
| $14$ | ||
| $15$ | ||
| $16$ | ||
| $17$ | ||
| $18$ | ||
| $19$ | ||
| $20$ |