A81673.奇怪的探针

$Alice$ 参加了一场奇怪的比赛。
比赛中，每条赛道都有一条长度为 $n$ 的信号轨。现在 Alice 有 $n$ 个不同强度的探针，需要将它们一一放置到位置 $1\ldots n$ 上
比赛给出了一些要求：对若干内点 $i$（$2\le i\le n-1$），规定其局部形态必须满足下述之一：

• 顶型要求 P：位置 $i$ 处必须是 $\{a_{i-1},a_i,a_{i+1}\}$ 中的严格最大；
• 底型要求 V：位置 $i$ 处必须是 $\{a_{i-1},a_i,a_{i+1}\}$ 中的严格最小。

边界位置不会有要求，同一位置也不会同时提出两类要求。除此之外，不再施加其他限制。

比赛组织者准备了多条赛道（多组数据）。Alice 想知道：对每条赛道，有多少种不同的强度布置方案满足全部要求？请你帮她计算，并将答案对 $998244353$ 取模。

第一行一个整数 $t$（测试组数）。

接下来对每组测试：

• 第一行一个整数 $n$（信号轨长度）。

• 第二行一个长度为 $n$ 的字符串 $s$，表示每个位置的形态要求：

  • '.' 表示该位置无要求；
  • 'P' 表示该位置有顶型要求；
  • 'V' 表示该位置有底型要求。

保证 $s_1 = s_n = '.'$，且输入不会出现同一位置同时为两类探针的矛盾描述。

对每组测试输出一行一个整数，表示满足约束的方案数对 $998244353$ 取模的结果。

数据范围

• $1 \le t \le 10$
• $1 \le n \le 3000$
• $\displaystyle \sum n \le 30000$