For this Question: <b> Update: The time limit for the problem has been updated to 5s.</b>

Bob is a prodigy. To avoid constant pestering, his professor has given him a non-negative integer N and the following task.

Bob needs to find out the smallest such <b>positive</b> integer X such that the product of the digits of X is exactly N. Obviously, this is not possible for many values of N. However, if the product is taken modulo 10<sup>9</sup>+7, the professor claims the answer exists for any value of N (in the range 0 to 10^9+6). Further, he claims that <b>the answer will not exceed 1000 digits</b>.

Alas! Bob solved it within twenty minutes. Can you?The first line of the input contains a single integer T, the number of test cases. (1 <= T <= 10)
The next T lines contain a single integer each, i<sup>th</sup> one being the value of N for the ith test case. (0 <= N <= 10<sup>9</sup>+6)Print the smallest positive number for which the product of digits modulo 10<sup>9</sup>+7 equals N. It is guaranteed that answer exists and contains <= 1000 digits.Sample Input:
2
12
0

Sample Output:
26
10

Explanation:

26 is the smallest positive integer with product of digits = 12.
For the second case, note that we need a positive integer and hence, answer is 10 and not 0., I have written this Solution Code: #include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define uint ungigned
#define db double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pli pair<ll,int>
#define vi vector<int>
#define vpi vector<pii >
#define IT iterator
 
#define PB push_back
#define MK make_pair
#define LB lower_bound
#define UB upper_bound
#define y1 wzpakking
#define fi first
#define se second
#define BG begin
#define ED end
 
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define UPD(x,y) (((x)+=(y))>=mo?(x)-=mo:233)
#define CLR(a,v) memset(a,v,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(a))
#define sqr(x) (1ll*x*x)
 
#define LS3 k*2,l,mid
#define RS3 k*2+1,mid+1,r
#define LS5 k*2,l,mid,x,y
#define RS5 k*2+1,mid+1,r,x,y
#define GET pushdown(k);int mid=(l+r)/2
#define INF (1ll<<60)
using namespace std;
const int mo=1e9+7;
int pri[4]={2,3,5,7};
int P[4][2333];
map<int,pii > mp;
int power(int x,int y){
	int s=1;
	for (;y;y/=2,x=1ll*x*x%mo)
		if (y&1) s=1ll*s*x%mo;
	return s;
}
void init(){
	For(i,0,3){
		P[i][0]=1;
		For(j,1,2100) P[i][j]=1ll*P[i][j-1]*pri[i]%mo;
		if (i<=1)
			For(j,0,2100) P[i][j]=power(P[i][j],mo-2);
	}
	Rep(i,2100,0) Rep(j,1400,0)
		if ((i+2)/3+(j+1)/2<=700)
			mp[1ll*P[0][i]*P[1][j]%mo]=pii(i,j);
}
int ans[12],tmp[12],v[4],V[4];
bool check(){
	if (tmp[0]!=ans[0]) return tmp[0]<ans[0];
	For(i,2,9) if (tmp[i]!=ans[i]) return tmp[i]>ans[i];
	return 0;
}
void update(int i,int j,int k,int l){
	For(i,0,9) tmp[i]=0;
	v[3]=i; v[2]=j; v[1]=k; v[0]=l;
	Rep(i,9,2){
		int x=i;
		For(j,0,3) V[j]=0;
		For(j,0,3) for (;x%pri[j]==0;x/=pri[j],V[j]++);
		int mn=100000;
		For(j,0,3) if (V[j]) mn=min(mn,v[j]/V[j]);
		tmp[i]=mn; tmp[0]+=mn;
		For(j,0,3) v[j]-=mn*V[j];
	}
	if (check())
		CPY(ans,tmp);
}
void solve(){
	int v;
	scanf("%d",&v);
	if (!v){
		puts("10");
		return;
	}
	if (v==1){
		puts("1");
		return;
	}
	ans[0]=700;
	v=power(v,mo-2);
	For(i,0,700) For(j,0,700)
		if (i+j<=ans[0]){
			int val=1ll*v*P[2][i]%mo*P[3][j]%mo;
			if (mp.find(val)==mp.end()) continue;
			int l=mp[val].fi,k=mp[val].se;
			if ((l+2)/3+(k+1)/2+i+j>=ans[0]) continue;
			update(j,i,k,l);
		}
	For(i,2,9) For(j,1,ans[i])
		putchar(i+'0');
	puts("");
}
int main(){
	init();
	int T; scanf("%d",&T);
	while (T--) solve();
}, In this Programming Language: C++, Now tell me if this Code is compilable or not?