#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; //#define int long long typedef long long ll; typedef unsigned long long ul; typedef unsigned int ui; const ll mod = 786433; const ll INF = mod * mod; typedef pairP; #define stop char nyaa;cin>>nyaa; #define rep(i,n) for(int i=0;i=0;i--) #define Rep(i,sta,n) for(int i=sta;i=1;i--) #define Rep1(i,sta,n) for(int i=sta;i<=n;i++) #define all(v) (v).begin(),(v).end() typedef pair LP; typedef long double ld; typedef pair LDP; const ld eps = 1e-12; const ld pi = acos(-1.0); ll mod_pow(ll x, ll n, ll m = mod) { ll res = 1; while (n > 0) { if (n & 1)res = res * x%m; x = x * x%m; n >>= 1; } return res; } struct rolling_hash { private: int sz; vector node; vector r; ll t = 999999937; ll m = 1000000009; ll invt; public: rolling_hash(const string &s) { int n = s.length(); sz = n; node.resize(n + 1); r.resize(n + 1); node[0] = 0; invt = mod_pow(t, m - 2, m); ll a = 1; rep(i, n) { //r[i] = a; int z = s[i] - 'a'; node[i + 1] = node[i] + a * z; node[i + 1] %= m; a = a * t%m; } a = 1; rep(i, n) { r[i] = a; a = invt * a%m; } } ll calc(int le, int len) { ll ret = node[le + len] - node[le]; if (ret < 0)ret += m; ret = ret * r[le] % m; return ret; } }; void manacher(const string &s, vector &r) { r.resize(s.size()); int i = 0, j = 0; while (i < s.size()) { while (i - j >= 0 && i + j < s.size() && s[i - j] == s[i + j])++j; r[i] = j; int k = 1; while (i - k >= 0 && i + k < s.size() && k + r[i - k] < j)r[i + k] = r[i - k], ++k; i += k; j -= k; } } map ps(string &s) { int n = s.size(); rolling_hash rs(s); //LP d1 =rs. calc(2, 1); //cout << d1.first << " " << d1.second << "\n"; map used; map next; map dp; //odd { vector c; manacher(s, c); rep(i, n) { int le = i + 1 - c[i]; int ri = i - 1 + c[i]; ll cur = rs.calc(le, ri - le + 1); dp[cur]++; used[cur] = true; while (le+1<=ri-1) { le++; ri--; ll nex = rs.calc(le, ri - le + 1); next[cur] = nex; if (used[nex])break; used[nex] = true; cur = nex; } } } //even { string ori; ori.push_back('#'); rep(i, n) { ori.push_back(s[i]); ori.push_back('#'); } vector c; manacher(ori, c); rep(i, n) { int le = i - c[2 * i] / 2; int ri = i - 1 + c[2 * i] / 2; if (le > ri)continue; ll cur = rs.calc(le, ri - le + 1); dp[cur]++; used[cur] = true; while (le + 1 <= ri - 1) { le++; ri--; ll nex = rs.calc(le, ri - le + 1); next[cur] = nex; if (used[nex])break; used[nex] = true; cur = nex; } } } queue q; map cnt; for (pair p : used) { if (next.find(p.first) != next.end()) { cnt[next[p.first]]++; } } for (pair p : used) { if (cnt[p.first]==0) { q.push(p.first); } } while (!q.empty()) { ll p = q.front(); q.pop(); if (next.find(p) != next.end()) { ll to = next[p]; dp[to] += dp[p]; cnt[to]--; if (cnt[to] == 0) { q.push(to); } } } return dp; } void solve() { string s, t; cin >> s >> t; map dps = ps(s), dpt = ps(t); ll ans = 0; for (pair p : dps) { ans += p.second*dpt[p.first]; } cout << ans << "\n"; } signed main() { ios::sync_with_stdio(false); cin.tie(0); //cout << fixed << setprecision(7); //init_f(); //init(); //experi(); //int t; cin >> t; rep(i, t)solve(); solve(); stop return 0; }