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
gaurav_2000: 2018-09-29 15:24:15

AC in one go!

daniel5399: 2017-11-09 15:47:52

Nice problem!

Last edit: 2017-11-09 15:48:20
deerishi: 2016-10-05 20:47:22

Nice problem!! O(n)!

mario_92: 2016-08-19 12:45:35

Last edit: 2016-08-19 12:48:50
rohitranjan017: 2016-08-18 05:48:37

Easy recursion !! AC in 0.00 in first go.

cnexans: 2016-08-07 07:03:09

I loved this question, although the test cases are weak. I have read the comments and tried to find a non recursive solution, but after a couple of WA I decided to do it recursively then I've got AC.

Last edit: 2016-08-07 07:05:13
hash7: 2016-06-30 16:08:10

Loved the question :D .. But took me 4 hrs to solve :( ... No recursion needed

minhthai: 2016-02-04 08:21:19

u can use stack if recursion tle

Zhaofeng: 2015-09-30 11:37:52

Nice question! Took me a bit of thinking but got AC in one go. I probably should practise more.

goku: 2015-09-26 09:53:55

it's weird my code gives right on 100's of test cases and the "stereotype"code gives RE for nnlnnlnlll still stereotype passes!!!???


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