COU  CounterSmack
Original problem statement (in Polish) can be found here.
Januarius the Clairvoyant recently started playing the popular, teambased online video game  CounterSmack. 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.
CounterSmack'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, teambased 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^{5}). ith letter indicates the ith 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.
hide comments
Piotr Jagie³³o:
20160406 15:01:33
Each input string is in a separate line, I edited the problem statement. Last edit: 20160406 15:07:49 

aqua_regia:
20160406 08:35:17
How are the input strings terminated? 
Added by:  Piotr Jagiełło 
Date:  20160405 
Time limit:  1s2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 
Resource:  PIZZA 2015 qualifying round 