BLKEK - Emoticon


When internet become popular, instant messaging is used by many people. Legend says that chat used to not be able to send image or stickers. So, users that want to express themself with more than word will have to use something called "smiley" or "emoticon" (it's called emoji now). Example of emoticons are :), :(, :v, XD, and :p.

Some people don't like that kind of emote because they have to be rotated, so they used something like  ^_^, T_T, x_x, and >=< (it's a giant enemy crab). Creativity rises as times passed, and emoticon starts using weird symbol that's not on a typical keyboard like ( ≧Д≦), (ノಠ益ಠ)ノ彡┻━┻, ( ͡° ͜ʖ ͡°), щ(゚д゚щ), and (っ˘ڡ˘)っ─∈. With hard to type emotes, some chatting site use word replace to change word into picture. For example, if someone types "Kappa" the site will change it to Kappa.

Henrik plans to create a chatting site that changes "KEK" to LUL. To increase that emote's appearance, Henrik will change every message containing the subsequence "KEK". For example, if someone types "BUKAHEHELAPAK" it will be changed because the subsequence "KEK" exists in that message. Henrik wants to know how many ways he can take the subsequence "KEK" in a message. For example, in  "BUKAHEHELAPAK" there are 2 ways to get the subsequence "KEK", using the bold letters in "BUKAHEHELAPAK" and "BUKAHEHELAPAK".

Input

First line is N, number of messages that need to be processed (N ≤ 1000). Next N line each contains a string containing the letter A-Z not more than 2000 letters in length.

Output

For each message, output the number of way subsequence "KEK" can be obtained.

Example

Input:
3
BUKAHEHELAPAK
KEKEK
KKE

Output:
2
4

hide comments
jarvis_1997: 2017-07-22 10:21:16

Just don't try this one. Repeat don't try. (But if you want points, this one will give 0.2 totally free ;)

vaibhavk31: 2017-06-28 19:09:44

Simple O(n) :)

vengatesh15: 2017-04-05 10:02:28

easy one did in O(n)..

shahzada: 2017-03-22 04:24:18

why the dp tag??
one of the easiest problem on spoj.
should be moved to tutorial.

govindgupta: 2017-01-12 09:19:07

my submission got rank 4:)

kira28: 2016-12-15 00:36:53

AC @0.05 sec :p

naskata929: 2016-10-24 16:19:08

O(N) gg easy :)

lalywr: 2016-10-14 20:24:55

array optimizations : 0.07 s :D

rajat_kumar: 2016-08-18 09:22:34

can anybody suggest what can be the largest possible solution to a testcase of this problem

Last edit: 2016-08-21 08:35:23
Piotr Jagie³³o: 2016-07-31 02:31:27

LUL


Added by:Andy
Date:2016-07-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:BLPCS3