WOWSUBSTR - Counting WOW-Substrings

no tags 

You are given a string. You have to count the total length of all WOW substrings. WOW substrings are defined as a contiguous substring of a string where there is not any character occurring more than one times. That means, all the characters of substring are unique.

As the answer could be very large, print it modulo 100007. (Note: 100007 is not a prime number.)

Input

Input starts with an integer T, denoting the number of test cases. Each case starts with a string S. All the characters in the string will be lowercase letters of the English alphabet.

Output

For each case, print the case number and total length of all WOW substrings of given string modulo 100007.

Constraints

1 <= T <= 50.

1 <= |S| <= 500000. (Length of string)

Example

Input:
2
aaa
ab

Output:
Case 1: 3
Case 2: 4

hide comments
nadstratosfer: 2020-02-24 16:14:34

-1 for silly TL. 0.2s won't let O(n) in Python get AC while a bruteforce in fast language wouldn't stand a chance with several times as much.

Please don't set TL below 1s in Classical.

shreyas0_0: 2016-11-27 14:21:06

I solved it on codechef IDE. I got correct answer for every different test case variation I tried. But here, it says time limit exceeded. :/ I am completely sure that my answer is correct. What should I do?

alfa_razra1505: 2016-11-22 14:46:56

anyone can give me corner test case ? my answer still getting WA :(

wisfaq: 2016-11-21 14:24:27

@Bishal:
thanks, I was being a little bit stupid.

BISHAL GAUTAM: 2016-11-21 13:26:20

@wisfaq; You have to count the total lengths of all WOW substrings.
So, for test2: 1+1+2=4

wisfaq: 2016-11-21 12:28:20

Could someone explain the two testcases?
This is what I can think up:
aaa: substrings a, a and a. Makes 3.
ab: substrings: a, b and ab. What is the 4th one?

Last edit: 2016-11-21 12:28:35

Added by:BISHAL GAUTAM
Date:2016-11-21
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:MySelf