Am not yet satisfied with the Welcome I have given to you guys :( No no, not so easy Welcome!! Lets try doing something harder, harder means more challenge, challenge leads to more excitement in life. So here I again welcome you with the same problem (somewhat more challenging this time). In a given string, you need to count the number of times the string "welcome to code" occurs as a subsequence. Since, this number can be very large this time, you just need to print the last 4 digits of the number.

Input

First line contains an integer t <= 100  the number of testcases. Each following line contains a string s of size >= 1 and <= 500 and containing only 'a'-'z' and spaces.

Output

For each testcase, output exactly 4 digits, the last 4 digits of the answer. If the answer < 1000, add as many '0' in the starting to make it exactly 4 digits. See Sample I/O for clarifications.

Example

Input:

3
pppp elcomew elcome to code
odkdnd wweellccoommee to code qps
welcome to code

Output:

0001
0128
0001