【POJ Challenge】我爱你啊

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

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

现在给出一些 ftiasch 的日记，问对于每篇日记，ftiasch 最多可能收到多少封情书。

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

输入格式

第 $1$ 行一个整数 $T$ ，表示日记的数量。

第 $2$ 到第 $T+1$ 行，每行是 ftiasch 的一篇日记。

输出格式

输出 $T$ 行，第 $i$ 行一个整数，表示第 $i$ 篇日记对应的最大可能的情书数量。

样例输入

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\le T\le 100$ ；
每篇日记只包含小写字母 a-z 和空格，长度小于 $100001$ 。

来源与许可

本题为 POJ Challenge 试题「我爱你啊」，题面与测试数据整理自 BZOJ 2295。

样例 1

输入

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

输出