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
aryan29: 2019-09-12 01:09:35

Adhoc AC in 1 go

navin_chandra: 2018-12-15 21:29:55

Solve this problem from the end of the string.

markaman: 2018-12-06 05:42:38

Surely not a dp simple thinking will give
You ac :)

k0walsk1: 2018-06-17 16:09:09

Using 2d dp and printf + scanf but getting TLE, any tips?

the_analyst753: 2018-06-03 13:10:07

not a dp question keep track on count of E and keep track on count of K

amitboss: 2018-03-26 09:19:35

O(n) sol , simple

zemotacqy: 2017-11-20 11:47:50

Really good question!!! Read the tags carefully......

burninggoku: 2017-09-20 14:45:44

first did using recursion..and then using 2d dp...

trump5377: 2017-08-22 18:11:34

AC in one go :) O(n)

aditya9125: 2017-07-26 08:38:42

O(n) dp, easy but enjoyed it.


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