The bear has a string s=s1s2... s|s| (record |s| is the string's length), consisting of lowercase English letters. The bear wants to count the number of such pairs of indices i,j (1≤i≤j≤|s|), that string x(i,j)=sisi+1... sj contains at least one string "bear" as a substring.
String x(i,j) contains string "bear", if there is such index k (i≤k≤j-3), that sk=b, sk+1=e, sk+2=a, sk+3=r.
Help the bear cope with the given problem.
The first line contains a non-empty string s (1≤|s|≤5000). It is guaranteed that the string only consists of lowercase English letters.
Print a single number − the answer to the problem.
bearbtear
6
bearaabearc
20
In the first sample, the following pairs (i,j) match: (1,4),(1,5),(1,6),(1,7),(1,8),(1,9).
In the second sample, the following pairs (i,j) match: (1,4),(1,5),(1,6),(1,7),(1,8),(1,9),(1,10),(1,11),(2,10),(2,11),(3,10),(3,11),(4,10),(4,11),(5,10),(5,11),(6,10),(6,11),(7,10),(7,11).