固定g(x)后，就变成了二次函数求极值问题。分情况讨论一下即可.

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N=1000002,INF=0x3f3f3f3f;

int a,b,c,d,n;
LL A,B;
vector<int> g[55];

LL f(int x)
{
	return A*x*x+B*x;
}

int main()
{
	for(int i=1;i<N;i++)
	{
		int tmp=i,sum=0;
		while(tmp) sum+=tmp%10,tmp/=10;
		g[sum].push_back(i);
	}	
	
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d%d%d%d",&a,&b,&c,&d,&n);
		
		LL ans=INF;
		for(int i=1;i<55;i++)
		{
			A=a*i+b, B=(LL)c*i*i+d*i;
			if(A<=0)
			{
				int x=upper_bound(g[i].begin(),g[i].end(),n)-g[i].begin()-1;
				if(x>=0) ans=min(ans,min(A*g[i][0]*g[i][0]+B*g[i][0],A*g[i][x]*g[i][x]+B*g[i][x]));
			}
			else
			{
				int l=0,r=upper_bound(g[i].begin(),g[i].end(),n)-g[i].begin()-1;
				if(!g[i].size()||l>r)continue;
				ans=min(ans,min(f(g[i][l]),f(g[i][r])));
				while(l<=r)
				{
					int m1=l+r>>1,m2=m1+r>>1;
					LL fm1=f(g[i][m1]),fm2=f(g[i][m2]);
					if(fm1>=fm2) l=m1+1;
					else r=m2-1;
					ans=min(ans,min(fm1,fm2));
				}
			}
		}
		
		printf("%lld\n", ans);
	}
	return 0;
}