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,
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 preorder 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 preorder 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 preorder 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:
20180929 15:24:15
AC in one go!


daniel5399:
20171109 15:47:52
Nice problem! Last edit: 20171109 15:48:20 

deerishi:
20161005 20:47:22
Nice problem!! O(n)! 

mario_92:
20160819 12:45:35
Last edit: 20160819 12:48:50 

rohitranjan017:
20160818 05:48:37
Easy recursion !! AC in 0.00 in first go. 

cnexans:
20160807 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: 20160807 07:05:13 

hash7:
20160630 16:08:10
Loved the question :D .. But took me 4 hrs to solve :( ... No recursion needed 

minhthai:
20160204 08:21:19
u can use stack if recursion tle 

Zhaofeng:
20150930 11:37:52
Nice question! Took me a bit of thinking but got AC in one go. I probably should practise more. 

goku:
20150926 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:  20130117 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 