Chef and Sign Sequences

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef found a strange string yesterday  a string of signs s, where each sign is either a '<', '=' or a '>'. Let N be the length of this string. Chef wants to insert N + 1 positive integers into this sequence and make it valid. A valid sequence is a sequence where every sign is preceded and followed by an integer, and the signs are correct. That is, if a sign '<' is preceded by the integer a and followed by an integer b, then a should be less than b. Likewise for the other two signs as well.
Chef can take some positive integers in the range [1, P] and use a number in the range as many times as he wants.
Help Chef find the minimum possible P with which he can create a valid sequence.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The only line of each test case contains the string of signs s, where each sign is either '<', '=' or a '>'.
Output
For each test case, output a single line containing an integer corresponding to the minimum possible P.
Constraints
 1 ≤ T, s ≤ 10^{5}
 1 ≤ Sum of s over all test cases in a single test file ≤ 10^{6}
Subtasks
Subtask #1 (30 points)
 1 ≤ T, s ≤ 10^{3}
 1 ≤ Sum of s over all test cases in a single test file ≤ 10^{4}
Subtask #2 (70 points)
 Original constraints
Example
Input: 4 <<< <>< <=> <=< Output: 4 2 2 3
Explanation
Here are some possible valid sequences which can be formed with the minimum P for each of the test cases:
1 < 2 < 3 < 4 1 < 2 > 1 < 2 1 < 2 = 2 > 1 1 < 2 = 2 < 3
Author:  berezin 
Editorial  https://discuss.codechef.com/problems/CHEFSIGN 
Tags  adhoc, berezin, cakewalk, greedy, july17 
Date Added:  18112015 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions