GLaDOS, the artificial intelligence of the Aperture Science Enrichment Center, decided to conduct another test for Chell. This time, the test is about cakes. GLaDOS arranged (n) cakes in a row. Each cake can be either real ( T ) or fake ( F ). Chell must guess which cakes are real and which are fake. Chell has a unique ability: she can determine exactly whether a cake is real just by looking at it. However, in her answer, she must satisfy GLaDOS's strange condition: all fake cakes in Chell's answer must form one contiguous subsegment (possibly empty). Initially, GLaDOS prepared some arrangement of cakes, but some cakes have not been placed yet. You are given a string (s) of length (n) describing the current situation: (s_i =) T , if the (i)-th cake is real; (s_i =) F , if the (i)-th cake is fake; (s_i =) N , if there is no cake at the (i)-th position yet, and GLaDOS may still place either a real or a fake cake there at her discretion. GLaDOS, being cunning, wants to make Chell's life harder. She wants to place the remaining cakes (replace all N with T or F ) so that the number of mistakes Chell is forced to make, under her optimal choice of segment, is as large as possible. Help GLaDOS determine the maximum number of mistakes she can guarantee. Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 10^4)). The description of the test cases follows. The first line of each test case contains one integer (n) ((1 \le n \le 500)) — the number of cakes. The second line of each test case contains a string (s) of length (n) consisting of the characters T , F , or N — the current arrangement of cakes. It is guaranteed that the sum of (n^3) over all test cases does not exceed (500^3). For each test case, output one integer — the maximum number of mistakes that GLaDOS can guarantee. In the first test case, (s =) FTFF , all cakes are already plac