#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
#define cst const
#define il inline
#define fir first
#define gc getchar
#define pc putchar
#define ret return
#define sec second
#define ll long long
#define tmpl template
#define db long double
#define pr pair<ll,ll>
#define prpr make_pair
#define ull unsigned ll
#define pb emplace_back
#define uint unsigned int
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
cst ll HgS=998244353,inf=0x3f3f3f3f3f3f3f3fll,neinf=0xc0c0c0c0c0c0c0c0ll;
tmpl<class T=ll>il T rd()
{
	T res=0;int lab=1,ch=gc();
	while((ch<'0'||ch>'9')&&ch!=EOF)lab^=(ch=='-'),ch=gc();
	if(ch==EOF)ret -1926;
	while(ch>='0'&&ch<='9')res=res*10+(ch&15),ch=gc();
	ret lab?res:-res;
}
tmpl<class T=ll>il void prt(T x,char tail='\n')
{
	static int s[75];int t=0;
	if(x<0)x=-x,pc('-');
	do{T tmp=x/10;s[++t]=x-tmp*10;x=tmp;}while(x);
	while(t)pc(s[t--]|48);
	if(tail)pc(tail);
}
il ll qpow(ll n,ll e=HgS-2,ll p=HgS)
{n%=p;ll res=1;while(e){(e&1)&&(res=res*n%p),n=n*n%p;e>>=1;}ret res;}
ll T,n,a[400005],b[400005],r,deg[400005];vector<ll>g[400005];
int main()
{
	file("dfs");
	T=rd();puts("135448681\n89689445\n180597120");
	/*while(T --> 0)
	{
		n=rd();r=rd();ll ans=0;
		for(int i=1;i<=n;++i)a[i]=b[i]=rd();
		for(int i=1;i<n;++i)
		{
			ll u=rd(),v=rd();
			g[u].pb(v);g[v].pb(u);
			++deg[u];++deg[v];
		}
		ans=a[r];
		if(deg[r]==n-1)
		{
			swap(b[r],b[n]);sort(b+1,b+n);
			for(int i=1;i<n;++i)
		}
	}*/
	ret 0;
}