如果把选择的字符串放到 trie 上，那么当且仅当选择的点能往上覆盖到根才能拼出所有字符串。
换句话说，记 $f_u$ 表示以 $u$ 为前缀的任意字符串能否被拼出，那么

\[f_u=f_u\space\mathrm{or}\space(f_{ls}\space\mathrm{and}\space f_{rs})\]

现在变成求方案数。

记 $f_u$ 表示以 $u$ 为前缀的任意字符串被拼出的方案数。

  • 如果 $u$ 不在全集里，那么其贡献就是 $f_{ls}\times f_{rs}$。
  • 如果 $u$ 在全集里，那么如果不选 $u$ 其贡献就是 $f_{ls}\times f_{rs}$，如果选了 $u$，那么其子树内任意一个字符串（除了 $u$ 本身）均可选或不选，贡献为 $2^{sz_u-1}$，其中 $sz_u$ 为 $u$ 子树中全集内字符串的数量。
#include<bits/stdc++.h>
#define siz(x) int((x).size())
#define all(x) std::begin(x),std::end(x)
#define fi first
#define se second
using namespace std;
using unt=unsigned;
using loli=long long;
using lolu=unsigned long long;
using pii=pair<int,int>;
mt19937_64 rng(random_device{}());
constexpr int P=998244353;
struct mint{
	int d;
	mint()=default;
	mint(int x):d(x){}
	friend std::istream&operator>>(std::istream&x,mint&y){return x>>y.d;}
	friend std::ostream&operator<<(std::ostream&x,mint y){return x<<y.d;}
	friend mint operator+(mint x,mint y){return (x.d+=y.d)<P?x.d:x.d-P;}
	mint&operator+=(mint z){return (d+=z.d)<P?d:d-=P,*this;}
	friend mint operator-(mint x,mint y){return (x.d-=y.d)<0?x.d+P:x.d;}
	mint&operator-=(mint z){return (d-=z.d)<0?d+=P:d,*this;}
	friend mint operator*(mint x,mint y){return int(1ll*x.d*y.d%P);}
	mint&operator*=(mint z){return d=int(1ll*d*z.d%P),*this;}
	static mint qpow(int x,int y=P-2){int z=1;for(;y;y>>=1,x=int(1ll*x*x%P))if(y&1)z=int(1ll*x*z%P);return z;}
	friend mint operator/(mint x,mint y){return x*=qpow(y.d);}
	mint&operator/=(mint z){return (*this)*=qpow(z.d);}
	friend mint operator^(mint x,mint y){return qpow(x.d,y.d);}
	mint&operator^=(mint z){return *this=qpow(d,z.d);}
	mint operator()(mint z)const{return qpow(d,z.d);}
	mint&operator[](mint z){return *this=qpow(d,z.d);}
	mint inv()const{return qpow(d);}
	mint pow(mint z)const{return qpow(d,z.d);}
	int operator+()const{return d;}
	mint operator-()const{return d?P-d:0;}
	int operator~()const{return ~d;}
};
mint operator""_m(lolu x){return mint(int(x%P));}
struct node{
	node *ls,*rs;
	mint f,g,h;
	node(){
		ls=rs=nullptr;
		f=g=h=0;
	}
	void upd(){
		h=(ls?ls->h:0)+(rs?rs->h:0)+g;
		f=(ls?ls->f:0)*(rs?rs->f:0)+(+g?2_m^(h-1):0);
	}
}*rt=new node;
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(false);cin.tie(nullptr);
	int T;cin>>T;while(T--){
		string s;cin>>s;
		node *p=rt;
		basic_string<node*>b;
		b.push_back(rt);
		for(char c:s){
			if(c=='A'){
				if(!p->ls)p->ls=new node;
				b.push_back(p=p->ls);
			}else{
				if(!p->rs)p->rs=new node;
				b.push_back(p=p->rs);
			}
		}
		b.back()->g=1;
		while(!b.empty()){
			b.back()->upd();
			b.pop_back();
		}
		cout<<rt->f<<'\n';
	}
	return 0;
}