I2. Kevin and Puzzle (Hard Version)
time limit per test
6 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

This is the hard version of the problem. The difference between the versions is that in this version, you need to count the number of good arrays. You can hack only if you solved all versions of this problem.

Kevin is visiting the Red Church, and he found a puzzle on the wall.

For an array $$$ a $$$, let $$$ c(l,r) $$$ indicate how many distinct numbers are among $$$ a_l, a_{l+1}, \ldots, a_r $$$. In particular, if $$$ l > r $$$, define $$$ c(l,r) = 0 $$$.

You are given a string $$$ s $$$ of length $$$ n $$$ consisting of letters $$$ \texttt{L} $$$ and $$$ \texttt{R} $$$ only. Let a non-negative array $$$ a $$$ be called good, if the following conditions hold for $$$ 1 \leq i \leq n $$$:

  • if $$$s_i=\verb!L!$$$, then $$$c(1,i-1)=a_i$$$;
  • if $$$s_i=\verb!R!$$$, then $$$c(i+1,n)=a_i$$$.

You need to count the number of good arrays $$$a$$$. Since the answer may be large, you only need to output the answer modulo $$$998\,244\,353$$$.

Input

Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1\le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2\leq n\leq 2\cdot 10^5$$$) — the length of string $$$s$$$.

The second line of each test case contains a string $$$s$$$ with a length $$$n$$$, containing only English uppercase letters $$$\verb!L!$$$ and $$$\verb!R!$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, output the number of good arrays modulo $$$998\,244\,353$$$.

Example
Input
4
3
LLR
3
RRL
4
RRLR
5
LLRLR
Output
1
2
0
1
Note

All arrays satisfying the conditions can be found in the easy version of this problem.