E. Испытание тортами
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

The cake is a lie.
— Portal

Гладос, искусственный интеллект Лаборатории исследования природы порталов, решила провести очередное испытание для Челл. На этот раз испытание связано с тортами.

Гладос расставила в ряд $$$n$$$ тортов. Каждый торт может быть либо настоящим (T), либо ложным (F). Челл должна угадать, какие торты настоящие, а какие ложные. Челл обладает уникальной способностью: она может точно определить, является ли торт настоящим, просто посмотрев на него. Однако в своём ответе она обязана удовлетворить странному условию Гладос: все ложные торты в ответе Челл должны образовывать непрерывный подотрезок (возможно, пустой).

Изначально Гладос подготовила некоторую расстановку тортов, но часть тортов ещё не размещена. Вам дана строка $$$s$$$ длины $$$n$$$, описывающая текущую ситуацию:

  • $$$s_i =$$$ T, если $$$i$$$-й торт настоящий;
  • $$$s_i =$$$ F, если $$$i$$$-й торт ложный;
  • $$$s_i =$$$ N, если на $$$i$$$-м месте торта пока нет, и Гладос ещё может поместить туда либо настоящий, либо ложный торт по своему усмотрению.
После того как Гладос завершит расстановку (заменит все N на T или F), Челл увидит окончательную расстановку и для каждого торта будет точно знать, настоящий он или ложный. Челл выберет такой непрерывный отрезок $$$[l, r]$$$ ($$$1 \le l \le r \le n$$$), который будет объявлен ею как множество ложных тортов (либо все торты будут объявлены настоящими). Все торты вне этого отрезка считаются настоящими. Челл хочет, чтобы её ответ был как можно ближе к истине, поэтому она выберет отрезок так, чтобы минимизировать количество ошибок.

Гладос, будучи коварной, хочет усложнить жизнь Челл. Она хочет расставить оставшиеся торты (заменить все N на T или F) так, чтобы количество ошибок, которое Челл неизбежно сделает при своём оптимальном выборе отрезка, было максимальным.

Помогите Гладос определить, какое максимальное количество ошибок она может гарантировать.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 500$$$) — количество тортов.

Вторая строка каждого набора входных данных содержит строку $$$s$$$ длины $$$n$$$, состоящую из символов T, F или N, — текущую расстановку тортов.

Гарантируется, что сумма значений $$$n^3$$$ по всем наборам входных данных не превосходит $$$500^3$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимальное количество ошибок, которое может гарантировать Гладос.

Пример
Входные данные
10
4
FTFF
5
TNFTT
6
TFTTTN
6
TNNFTF
7
TNFNTNF
6
NNFFNN
7
TNTFNTN
1
N
5
NNNNN
10
NNNTTNNNFN
Выходные данные
1
0
1
2
2
2
2
0
2
3
Примечание

В первом наборе входных данных $$$s =$$$ FTFF, все торты уже расставлены. Челл выберет отрезок $$$[3, 4]$$$, то есть даст ответ TTFF, и у неё будет $$$1$$$ ошибка.

Во втором наборе входных данных $$$s =$$$ TNFTT, не расставлен $$$1$$$ торт. При любой замене N на T или F ложные торты образуют непрерывный отрезок, который может выбрать Челл, поэтому ответ равен $$$0$$$.

В третьем наборе входных данных $$$s =$$$ TFTTTN. Гладос заменит N на F, получив TFTTTF. Можно показать, что ответ не меньше $$$1$$$. Если Челл выберет отрезок $$$[2, 2]$$$, то есть даст ответ TFTTTT, то она допустит ровно $$$1$$$ ошибку.

В четвёртом наборе входных данных $$$s =$$$ TNNFTF. Гладос расставит торты следующим образом: TFTFTF. Челл выберет отрезок $$$[2, 4]$$$ (ответ TFFFTT), допустив $$$2$$$ ошибки.