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
2015-05-29 04:59:52 swap
Did it..!! But can we find the depth of the nice binary tree from its post-order and in-order traversal ??
2015-03-02 16:21:25 Shubham Jadhav
Seems difficult but one property of "nice" binary trees makes it easy. :)
2015-01-30 18:00:14 Amogh
nice problem AC in one go :)
2015-01-18 06:59:18 deepak garg
good one
2014-12-31 22:22:51 Yashpal
Nice Question !! :)
2014-12-01 13:54:19 vb
Nice Recursion :)
2014-09-08 14:27:58 Richa Jain
I am using recursion but getting TLE again and again.. please help!
2014-07-24 22:24:24 Hammad Akhtar
easy peasy ;}
AC in one go.
recursion.
2014-07-15 13:07:45 master_blaster
can anyone please check my code. link is <snip> . i am getting wa even though all test cases are working fine

Last edit: 2023-05-22 13:45:05
2014-07-09 14:42:47 Archit Jain
nice and easy
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.