UOJ Logo FLYIOI UOJ

FLYIOI

#37. 无聊的会议

时间限制:

1s;内存限制 128MB

题目描述:

土豪学长作为一名光荣的学生会干部,每天要参加很多无聊的会议。他发现:他开会的会议桌一定是正n边形,n个干部坐在这个多边形顶点上。因为太无聊了,所以他想要数出所有的“完全”等腰三角形——这种等腰三角形的三个顶点一定全是给出n多边形的顶点,且三个顶点上坐的干部性别相同。
土豪学长是土豪,他用1000000000%10的佣金雇用你,让你帮他数。PS:如果两个“完全”等腰三角形三个顶点相同,计算时只算一个。

输入描述:

第一行一个数字T,表示有T组数据。
接下来有T组数据,每组数据共一行。这一行给出一个长度为n的字符串,表示正n边形n个顶点上干部的性别。1为男,0为女。

输出描述:

对于第i组数据:输出”Case i: ans”(不带引号),ans为“完全”等腰三角形的数量。

样例输入:

5
0001
01
10001
1101010
111010

样例输出:

Case 1: 1
Case 2: 0
Case 3: 1
Case 4: 3
Case 5: 2

数据范围:

40%的数据保证n<=20
100%的数据保证 n<=10^6
所有数据保证T<=10