#pragma comment(linker, "/STACK:102400000,102400000") #include #include #include #include #include #define M 8000005 #define N 200005 #define K 20 using namespace std; const int Mo=(int)1e9+7; long long SUM; int i,j,m,n,p,k,fox[N][K],a[N],Min[N],vis[N],flag,Que[N],K1; int x,y,k1,te[N],fa[N],deep[N],Q[N],Sum[N],F[N],Fox[N]; struct Node{int ed,before;}s[M],S[N*2]; void add(int x,int y) { S[++K1].ed=y;S[K1].before=Fox[x];Fox[x]=K1; } void pre() { memset(Min,60,sizeof(Min)); for (i=2;i'9'); x=c-'0'; while (c=getchar(),c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-'0'; return x; } void insert(int x,int y,int z) { s[++k1].ed=z; s[k1].before=fox[x][y]; fox[x][y]=k1; } int power(int x,long long y) { int sum=1; for (;y;y>>=1) { if (y&1) sum=1ll*sum*x%Mo; x=1ll*x*x%Mo; } return sum; } void dfs(int x) { int i; for (i=Fox[x];i;i=S[i].before) if (fa[x]!=S[i].ed) { int p=S[i].ed; fa[p]=x; deep[p]=deep[x]+1; dfs(p); } } inline bool cmp(int a,int b) { return deep[a]>deep[b]; } void Work(int x,int y) { Q[0]=0; int i; for (i=fox[x][y];i;i=s[i].before) Q[++Q[0]]=s[i].ed; ++flag; for (i=1;i<=Q[0];++i) Sum[Q[i]]=1,F[Q[i]]=flag; for (i=1;i<=Q[0];++i) { int p=Q[i]; if (F[fa[p]]==flag) Sum[fa[p]]+=Sum[p]; else SUM+=1ll*Sum[p]*(Sum[p]-1)/2+Sum[p]; } } void doit() { Que[Que[0]=1]=1; int l; for (l=1;l<=Que[0];++l) { p=Que[l]; for (i=Fox[p];i;i=S[i].before) if (fa[p]!=S[i].ed) Que[++Que[0]]=S[i].ed; } } int main() { // freopen("1.in","r",stdin); // freopen("1.out","w",stdout); int T; scanf("%d",&T); pre(); for (;T--;) { memset(fox,0,sizeof(fox)); k1=0; flag=0; memset(Fox,0,sizeof(Fox)); K1=0; memset(F,0,sizeof(F)); scanf("%d",&n); for (i=1;i1;j/=Min[j]) { if (last!=Min[j]) last=Min[j],sum=1; else sum++; insert(last,sum,i); //printf("%d\n",sum); } } //printf("%d\n",k1); int Ans=1,ans=1; for (i=2;i1;j/=Min[j]) { if (last!=Min[j]) last=Min[j],sum=1; else sum++; insert(last,sum,i); //printf("%d\n",sum); } } //printf("%d\n",k1); for (i=2;i