+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- After human-beings arrived at Mars, they discovered the existence of aliens! What is more fascinating is that aliens had traffic lights just like we do. But traffic lights on Mars didn’t work the way they do on the Earth. On the Earth, traffic lights follow a particular sequence, green yellow, red, green, yellow red and so on. Humans got bored on space and decided to play a game. They recorded the sequence of colours on a traffic light from time $1$ to time $N$ (inclusive), then created a sequence $S$ of length $N$ (`G` stands for Green, `Y` stands for Yellow, and `R` stands for Red). The value of $S_i$ determines the colour of the traffic light at time $i$. Now humans want to extract a subsequence out of this sequence which should be valid according to traffic light rules on planet Earth (following the valid pattern), and have the maximum length possible. Help them achieve this task (green can be followed by green or yellow, yellow can be followed by yellow or red, and red can be followed by red or green). # ورودی The first line consists of $T$, the number of test cases. $$1 \leq T \leq 100$$ First line of each test contains an Integer $N$. $$1 \leq N \leq 10^5$$ Second line of each test case contains string $S$ consisting of letters `R`, `Y`, `G`. # خروجی The output consists of $T$ lines, each line containing the length of longest valid subsequence. # مثال‌ها ## ورودی نمونه ۱ ``` 2 7 YYRGRGG 7 RRRRGYY ``` ## خروجی نمونه ۱ ``` 6 7 ``` In the first test case the resulting subsequence would be: `YYRRGG`.