Original problem statement (in Polish) can be found here.

Januarius the Clairvoyant recently started playing the popular, team-based online video game - Counter-Smack. His paranormal abilities are certainly a big help during the gameplay, but even having a keen inner eye is not enough when all of your teammates are total noobs. There's just no way to climb up the ranking when something like this happens.

Counter-Smack's ranking system is really simple. The player starts with zero points. For every win he gains a point, for every defeat he loses a point. Of course the more points, the better.

One may think that using the gift of clairvoyance you could detect the noobs in advance, and just skip the game in case they would join your team. Unfortunately, that's not how the laws of the universe work, and Januarius knows that. As it turns out, team-based online games are one of the few cases where the Primeval Law of Destiny applies - it may just so happen that you will be joined by noobs in the next game and you can't do anything about it, as it is already written down in the Universum's atoms.

Fortunately, there is a loophole. You can join the game and immediately leave, and the destiny will be fulfilled. Even though you lose a point for leaving the game (just as in the case of simply losing), you are additionally banned for a few next games - and being banned also fulfills the destiny.

Using his abilities, Januarius can predict the future for the next n games - he will know whether he will be joined by the noobs or not. When leaving the game for the first time, the player is banned for the next one. Leaving for the second time will get you banned for the next two games. Leaving for the third time results in a ban that lasts for four games, and so on - every ban is twice as long as the previous one.

What is the maximum number of points Januarius can achieve in n succesive games, if he starts with zero points, he wins every match without the noobs on his team, and loses all the other matches?

Input

The first line contains a single integer t, denoting the number of testcases. Then, testcases follow, each in a separate line.

Each testcase consists of a string of length n, describing the predicted future for the next n games. (1 <= n <= 2*10⁵). i-th letter indicates the i-th game. "N" means that Januarius will be joined by the noobs in this game, "P" denotes good players.

Output

For each testcase you should output a single integer - the maximum number of ranking points that Januarius can achieve by abandoning some of the matches.

Example

Input:

4
PPPPP
PPPPN
NNPPP
NNNNN

Output:

5
3
2
-2

Explanation

In the third testcase, by abandoning the first game, Januarius will be banned for the next one. He will win the rest of them, so his final result will be (-1)+3 = 2 points.

In the fourth testcase, Januarius can abandon the first game, which will get him banned for the next one. Then he can abandon another game, and this time he will get banned for the last two games. His final score will be -2 points, for abandoning two games.