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