WLCME - Welcome To Code - Easy

Since I didn't get any chance to welcome you all to this NOVICE Contest for NSIT and IIITA, I got a chance here to welcome you all :). So here's the algorithmic way of welcoming you all. In a given string of characters, you need to count the number of times the string "welcome to code" occurs as a subsequence. Please note that a string is called a subsequence of another string if the first one can be obtained by deleting zero or more characters from the second string. For instance, "hlwrld" is subsequence of "hello world".

Input

First line of Input contains an integer t <= 100 - the number of testcases. Following each line contains a string s of size >= 1 and <= 30 and containing 'a'-'z' and spaces only.

Output

For each testcase, print the number of times 'welcome to code' occurs in the given string.

Example

Input:
3
elcomew elcome to code
wweellccoommee to code qpsd
welcome to code

Output:
1
128
1

Added by:Ankul Garg
Date:2011-02-05
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.