NICEBTRE - Nice Binary Trees

no tags 

 

For example, the following tree is nice,
but the following tree is not.
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”.

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

hide comments
Archit Jain: 2014-07-09 14:42:47

nice and easy

vikrant: 2014-07-02 14:43:58

Recursion :)

heatOn: 2014-06-05 09:07:24

Nice One :)

Saurav Shekhar: 2014-05-18 10:00:19

I am unable to see the images. Maybe because they are not there at the original page anymore. @problem setter please see to it. You can use the images hosted at this link http://www.bnuoj.com/contest/problem_show.php?pid=28810
--ans(Francky)--> I can do it. Done.

Last edit: 2014-05-18 10:51:29
sarelfeniel: 2014-04-21 16:48:49

Great problem. Nice and easy but still satisfying.

codestorm: 2014-02-19 09:04:03

recursion

Piyush Raman Srivastava: 2014-01-22 14:51:41

common interview question!!

Anant Kumar: 2013-12-23 14:50:16

nice one.

Ashwini: 2013-12-23 10:26:35

giving all answers right in my pc. why wa here??????????
any tricky test cases?
Help me....
<snip>

Last edit: 2023-05-22 13:44:39
prudhvi: 2013-10-26 12:39:31

Easy one but before attempting check the definition of pre-order traversal


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