//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
//#pragma GCC target("bmi,bmi2,popcnt,lzcnt")
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <fstream>
#include <climits>
#include <queue>
#include <algorithm>
#include <stdint.h>
#include <stack>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <cstring> // Для memset
#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pii;
typedef pair <ld, ld> pdd;
const ll DIM = 700007;
const ll MXMASK = (1 << 21);
const ll INF = 1e18;
const ll mod = 998244353;
const ld eps = 0.00000000001;
const ld gr = (sqrt(5) + 1) / 2;
const ll offset = 10000;
const ll Bits = 20;
const ll dx[4] = { 1, 0, -1, 0 };
const ll dy[4] = { 0, 1, 0, -1 };
FILE* stream;
ll P;
string check(ll o, ll c, const string& s) {
string p;
for (int j = 0; j < s.length(); j++) p += "0";
ll x = 0;
for (int j = 0; j < s.length(); j++) {
if (x == o) break;
if (s[j] == '(') {
p[j] = 'G';
x++;
}
}
x = 0;
for (int j = s.length() - 1; j >= 0; j--) {
if (x == c) break;
if (s[j] == ')') {
p[j] = 'G';
x++;
}
}
ll v1 = 0, v2 = 0;
bool flag = true;
for (int j = 0; j < s.length(); j++) {
if (p[j] == 'G') {
if (s[j] == '(') { v1++; v2++; }
if (s[j] == ')') { v1--; v2--; }
}
else {
if (s[j] == '(') {
if (v1 < v2) {
v1++;
p[j] = 'B';
}
else {
v2++;
p[j] = 'R';
}
}
else {
if (v1 > v2) {
v1--;
p[j] = 'B';
}
else {
v2--;
p[j] = 'R';
}
}
}
if (v1 < 0 || v2 < 0) flag = false;
}
if (v1 == 0 && v2 == 0 && flag) {
return p;
}
return "-1";
}
string solve1(const string &s) {
ll open = 0, close = 0;
ll val = 0;
for (int i = 0; i < s.length(); i++) {
if (s[i] == '(') {
val++;
open++;
}
else {
val--;
close++;
}
}
if (val >= 0) {
for (int i = val; i <= close; i++) {
ll o = i - val;
if (check(o, i, s) != "-1") {
return check(o, i, s);
}
}
return "impossible";
}
else {
val *= -1;
for (int i = val; i <= open; i++) {
ll c = i - val;
if (check(i, c, s) != "-1") {
return check(i, c, s);
}
}
return "impossible";
}
}
ll res[20];
void solve2() {
ll n;
cin >> n;
cout << res[n] << endl;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//freopen_s(&stream, "input.txt", "r", stdin);
//freopen_s(&stream, "output.txt", "w", stdout);
for (int i = 1; i <= 15; i++) {
for (int j = 0; j < (1 << i); j++) {
ll m = j;
string s;
for(int k = 1; k <= i; k++) {
if (m & 1) {
s += ")";
}
else s += "(";
m >>= 1;
}
string p = solve1(s);
if (p != "impossible") res[i]++;
res[i] %= mod;
}
}
cin >> P;
ll T;
cin >> T;
while (T--) {
if (P == 1) {
string s;
cin >> s;
cout << solve1(s) << endl;
}
if (P == 2) solve2();
}
return 0;
}
