#include
using namespace std;
#define _l (long long int)
const int maxn = 2000009; const int mod = (1 « 23) * 7 * 17 + 1;
int n, a[maxn], b[maxn], c[maxn];
int readInt(int* a) { static char g[maxn]; scanf("%s", g); int l(strlen(g)); for (int i = 0; i < l; ++ i) a[l - i - 1] = g[i] - 48; return l; }
int modPow(int a, int x) { int s(1); for (; x; x »= 1, a = _l a * a % mod) if (x & 1) s = _l s * a % mod; return s; }
void fnt(int* a, int n, int rv) { for (int i = 1, j = n » 1, k; i < n - 1; ++ i) { if (i < j) swap(a[i], a[j]); for (k = n » 1; j >= k; k »= 1) j -= k; if (j <= k) j += k; } for (int l = 2; l <= n; l «= 1) { int w0(modPow(3, (mod - 1) / l)); if (rv) w0 = modPow(w0, mod - 2); for (int i = 0; i < n; i += l) { int w(1); for (int j = i; j < i + (l » 1); ++ j) { int x(a[j]), y(_l a[j + (l » 1)] * w % mod); a[j] = (x + y) % mod; a[j + (l » 1)] = (x - y + mod) % mod; w = _l w * w0 % mod; } } } if (rv) { int ninv(modPow(n, mod - 2)); for (int i = 0; i < n; ++ i) a[i] = _l a[i] * ninv % mod; } }
void sov() { memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); int tl(max(readInt(a), readInt(b))); for (n = 1; n < tl * 2; n «= 1); fnt(a, n, 0); fnt(b, n, 0); for (int i = 0; i < n; ++ i) c[i] = _l a[i] * b[i] % mod; fnt(c, n, 1); for (int i = 0; i < n; ++ i) { c[i + 1] += c[i] / 10; c[i] %= 10; } int x; for (x = n - 1; x && !c[x]; – x); for (; x >= 0; – x) putchar(c[x] + 48); putchar(10); }
int main() { #ifndef ONLINE_JUDGE // freopen(".in", “r”, stdin); #endif
int t;
scanf("%d", &t);
while (t --)
sov();
}