A Ribbon for Tomorrow

Problem

You are given a binary string s of length n. You may apply the following operation any number of times, including zero:

• choose two indices l and r such that 1 ≤ l ≤ r ≤ n and, in the current string, s[l] = s[r];
• reverse the order of the characters in the substring s[l..r].

Determine how many distinct binary strings can be obtained from s. Return the answer modulo 998244353.

Input

The first line contains the number of test cases t.

For each test case:

1. one line contains the integer n;
2. the next line contains a binary string s of length n.

Output

For each test case, print one integer: the number of distinct binary strings reachable from s, modulo 998244353.

Constraints

• 1 ≤ t ≤ 10^4.
• 1 ≤ n ≤ 10^6.
• s contains only 0 and 1 and has length n.
• The sum of n over all test cases does not exceed 10^6.
• Time limit: 2 seconds.
• Memory limit: 256 MB.

Notes

The condition s[l] = s[r] is evaluated on the current state of the string, after all previously applied operations.