Background

Special for beginners, ^_^

Description

ftiasch是个十分受女生欢迎的同学，所以她总是收到许多情书。虽然她十分有魅力，然而她却是个低调的人。因此她从来不会告诉别人她到底收到了多少情书。

ftiasch的好朋友1tthinking想知道她到底收到了多少情书。1tthinking知道，ftiasch每次收到一封情书，就会在日记最后写下一个包含"luvletter"子序列的串。比如现在ftiasch的日记是alduddvdletterflusvletetedr，那么ftiasch可能受到了0、1、2封情书。现在给出一些ftiasch的日记，问对于每篇日记，ftiasch最多可能受到多少的情书。

某个序列的子序列是从最初序列通过去除某些元素但不破坏馀下元素的相对位置而形成的新序列。參考wikipedia。

Format

Input

第1行，一个整数 T (0 ≤ T ≤ 100), 日记的数量。第2到 T + 1行，ftiasch的日记 (只包含'a'-'z' 和空格, 长度小于100001)

Output

第1到T行，一个整数, 最大可能的情书数量。

Samples

5
t
llllluvletterrr
luvletterlauavalaeatataearaluvletter
is wzk a famous boy yes buz he always receives a lot of luv letters
my heart beats her waves at the shore of the world and writes upon it her signature in tears with the words i love thee

0
1
3
1
0

Limitation

1s, 1024KiB for each test case.