NICEBTRE - Nice Binary Trees

Binary trees can sometimes be very difficult to work with. Fortunately, there is a class of trees with some really nice properties. A rooted binary tree is called “nice”, if every node is either a leaf, or has exactly two children.

For example, the following tree is nice,

nice tree

but the following tree is not.

not a nice binary tree

The leaves of a nice binary tree are labeled by the letter ‘l’, and other nodes are labeled by the letter ‘n’.

Given the pre-order traversal of a nice binary tree, you are required to find the depth of the tree.

Notes:

  1. The depth of a tree is defined as the length of the longest path with one end at the root.
  2. The pre-order traversal of the tree in the first image above produces the string “nlnnlll”.

Input

The first line contains the number of test cases T. T lines follow. Each line contains a string, which represents the pre-order traversal of a “nice” binary tree. Leaves are represented by the letter ‘l’ and other nodes by the letter ‘n’. The input is guaranteed to be the preorder traversal of a nice binary tree.

Output

Output one line for each test case, containing a single integer, the depth of tree.

Constraints

0 < T < 20

Length of the input string in each test case is at most 10000.

Example

Input:
3
l
nlnll
nlnnlll

Output:
0
2
3

Added by:Anil Shanbhag
Date:2013-01-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2013-08-18 16:28:20 Alien
easy prob....
2013-07-01 23:13:31 rishabhshinghal
AC in first attempt:P
2013-06-02 10:08:24 Atul Kumar Verma
Very Nice Question :)
2013-05-14 12:11:44 Anuj_LuckFove!
one beautiful concept of traversal in trees.. and AC :P
2013-03-11 17:23:01 K.P.
Any tricky test case...?
2013-03-10 17:17:01 Monkey D. Luffy
any tricky test case ??
2013-02-02 12:13:56 Amrit
id 8640086 ? tricky cases plz??
2013-01-27 04:09:26 shadoww
@Anil can you check sol 8594086 why its giving wrong answer :(
Any tricky test cases ???

Finally Got AC :)..


Last edit: 2013-01-28 08:47:55
2013-01-23 13:45:57 (Tjandra Satria Gunawan)(曾毅昆)
183B in python3... :-)
EDIT: 178B
EDIT2: 0.00s in python2 ;-)

edit: you are really cocky man, this problem is not that complex

Last edit: 2013-02-27 01:19:45
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.