從開始寫到現在 遇到最悲劇的一題
這題只能暴力猛剪枝
用了前綴標記，跟對角線的標記縮短速度
23 1
23 3
這兩筆測資過不了…
只好壓縮答案 (答案很大，我用 62 進位) 才過
//====================================================================||
// ||
// ||
// Author : GCA ||
// 6AE7EE02212D47DAD26C32C0FE829006 ||
//====================================================================||
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cctype>
#include <utility>
using namespace std;
#ifdef ONLINE\_JUDGE
#define ll "%lld"
#else
#define ll "%I64d"
#endif
typedef unsigned int uint;
typedef long long int Int;
#define Set(a,s) memset(a,s,sizeof(a))
#define Write(w) freopen(w,"w",stdout)
#define Read(r) freopen(r,"r",stdin)
#define Pln() printf("\\n")
#define I\_de(x,n)for(int i=0;i<n;i++)printf("%d ",x\[i\]);Pln()
#define De(x)printf(#x"%d\\n",x)
#define For(i,x)for(int i=0;i<x;i++)
#define CON(x,y) x##y
#define Pmz(dp,nx,ny)for(int hty=0;hty<ny;hty++){for(int htx=0;htx<nx;htx++){\\
printf("%2d ",dp\[htx\]\[hty\]);}Pln();}
#define M 100005
#define PII pair<int,int\>
#define PB push\_back
#define oo INT\_MAX
#define Set\_oo 0x3f
#define Is\_debug true
#define debug(...) if(Is\_debug)printf("DEBUG: "),printf(\_\_VA\_ARGS\_\_)
#define FOR(it,c) for(\_\_typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define eps 1e-6
bool xdy(double x,double y){return x>y+eps;}
bool xddy(double x,double y){return x>y-eps;}
bool xcy(double x,double y){return x<y-eps;}
bool xcdy(double x,double y){return x<y+eps;}
int min3(int x,int y,int z){
int tmp=min(x,y);
return min(tmp,z);
}
int max3(int x,int y,int z){
int tmp=max(x,y);
return max(tmp,z);
}
int seize\[M\];
int sall\[M\];
int mz\[10\]\[10\];
int s\[50\]\[M\];
char strnum\[M\]\[20\];
int snum\[50\],tl,sum;
vector<int\> spnum\[50\]\[3\]\[105\];
int head\[50\]\[M\];
int ls\[50\]\[10\]\[50\];
string ans\[1000\];
int nans;
int line\[10\];
int add(int x){
char str\[100\];
int ans=0;
sprintf(str,"%d",x);
int len=strlen(str);
for(int i=0;i<len;i++){
ans+=str\[i\]-'0';
}
return ans;
}
void pre(){
Set(seize,0);
Set(sall,0);
Set(snum,0);
Set(head,0);
Set(s,0);
for(int i=2;i<M;i++){
if(!seize\[i\]){
if(i>=10000){
int t=add(i);
sprintf(strnum\[i\],"%d",i);
s\[t\]\[snum\[t\]++\]=i;
for(int j=0;j<3;j++){
int k=(strnum\[i\]\[j\]-'0')\*10+(strnum\[i\]\[4-j\]-'0');
spnum\[t\]\[j\]\[k\].PB(i);
}
int tt=0,tt2=0;
for(int j=0;j<5;j++){
tt=tt\*10+strnum\[i\]\[j\]-'0';
tt2+=strnum\[i\]\[j\]-'0';
head\[t\]\[tt\]=1;
ls\[t\]\[j\]\[tt2\]=1;
}
}
for(int j=i+i;j<M;j+=i){
seize\[j\]=1;
}
}
}
}
bool first;
void dfs(int d1,int d2,int dep){
if(dep==5){
for(int i=0;i<5;i++){
for(int j=0;j<5;j++)ans\[nans\].PB(mz\[i\]\[j\]+'0');
}
nans++;
return ;
}
int k,j;
if(dep==0){
k=0;
j=(strnum\[d1\]\[0\]-'0')\*10+(strnum\[d2\]\[4\]-'0');
}
else if(dep==1){
k=1;
j=(strnum\[d1\]\[1\]-'0')\*10+(strnum\[d2\]\[3\]-'0');
}
else if(dep==2){
k=2;
j=(strnum\[d1\]\[2\]-'0')\*10+(strnum\[d2\]\[2\]-'0');
}else if(dep==3){
k=1;
j=(strnum\[d2\]\[1\]-'0')\*10+(strnum\[d1\]\[3\]-'0');
}
else if(dep==4){
k=0;
j=(strnum\[d2\]\[0\]-'0')\*10+(strnum\[d1\]\[4\]-'0');
}
int size=spnum\[sum\]\[k\]\[j\].size();
for(int i=0;i<size;i++){
int now=spnum\[sum\]\[k\]\[j\]\[i\];
// printf("%s\\n",strnum\[now\]);
for(int jj=0;jj<5;jj++){
mz\[dep\]\[jj\]=strnum\[now\]\[jj\]-'0';
}
bool canput=true;
for(int jj=0;jj<5;jj++){
int a=line\[jj\]\*10+mz\[dep\]\[jj\];
//printf("%d ",line\[jj\]);
if(!head\[sum\]\[a\]){
canput=false;
break;
}
}
if(canput){
for(int jj=0;jj<5;jj++)line\[jj\]=line\[jj\]\*10+mz\[dep\]\[jj\];
dfs(d1,d2,dep+1);
for(int jj=0;jj<5;jj++)line\[jj\]=line\[jj\]/10;
}
}
return ;
}
void xprint(int x){
vector<int\> f;
for(int i=x;i>0;i/=62){
f.PB(i%62);
}
for(int i=f.size()-1;i>=0;i--){
int t=f\[i\];
if(t<10)printf("%d",t);
else if(t<36)printf("%c",'A'+t-10);
else if(t<62)printf("%c",'a'+t-36);
}
}
void solve(){
nans=0;
for(int i=0;i<1000;i++)ans\[i\].clear();
int d1,d2;
for(int i=0;i<snum\[sum\];i++){
for(int j=0;j<snum\[sum\];j++){
if(strnum\[s\[sum\]\[i\]\[2\]==strnum\[s\[sum\]\[j\]\[2\]&&strnum\[s\[sum\]\[i\]\[0\]==tl+'0'){
d1=s\[sum\]\[i\];
d2=s\[sum\]\[j\];
//debug("%d %d\\n",d1,d2);
Set(line,0);
Set(mz,0);
dfs(d1,d2,0);
}
}
}
sort(ans,ans+nans);
for(int i=0;i<nans;i++){
int size=ans\[i\].size();
if(i)Pln();
for(int j=0;j<size;j++){
printf("%c",ans\[i\]\[j\]);
if(j%5==4)Pln();
}
}
/\*
for(int i=0;i<nans;i++){
int size=ans\[i\].size(),t=0;
for(int j=0;j<size;j++){
if(t<10000){
t=t\*10+ans\[i\]\[j\]-'0';
if(j==size-1){
xprint(t);
}
}else{
xprint(t);
t=ans\[i\]\[j\]-'0';
}
}
}\*/
}
void decode(char str\[\]){
int len=strlen(str);
int t=0;
int npn=0;
bool first=true;
for(int i=0;i<len;i++){
if(t<10000){
if(str\[i\]<='z'&&str\[i\]>='a')t=t\*62+str\[i\]-'a'+36;
else if(str\[i\]<='Z'&&str\[i\]>='A')t=t\*62+str\[i\]-'A'+10;
else t=t\*62+str\[i\]-'0';
}
if(t>=10000||i==len-1){
if(npn==0){
if(!first)Pln();
first=false;
}
printf("%d\\n",t);
npn=(npn+1)%5;
t=0;
}
}
}
struct{
int s,t;
char \*pref;
}fpre\[\]{
//{11,1,"2x53eL7t5Dq53Sj2x58dX7t53eL8fH3Sj3ON8P1D4B3T1"},
{23,1,"2xrJivGYxMFP4yh2xrOfDGYxHJ74yh36ZG7NI3rODL4yh3FHDWFPrFIpT51b3FHMYZH0XKYt36Z3GjMoXAC76UTNhz3GjOAjECLJoR51b3LxEsRJ9nIuhAAx3NPNjREUvF9r9iD3U5JivI0f6hXIYd3Y94YZJvzIMRK4h3Zt7BRGovD6hPmt3Zt9l7GovAX1Pmt3b3G7NMSlJH351b3b3H4tI2PJ8L8d93b3HTZLzjIEJ5BB3b3I3rJMrGfL8mj3bvKc5GkH6wvIYd3jlHfBEsR6UTNhz3mf7mbAX1NnDKaL3mfAMHAX1LDXKaL3mfF0rH4bAX1K4h3oPLtvH39Igl51b3oPOarDRbJeH4yh3pr53LNox7ynPmt3qRJrLGY560ZKDP3sBMiRIQnCm58gL3yHEzhMVfM2L2xr3yHFVdAYTFr7KaL3zjEzhJuXOc12xr41TDWFMFPLf751b41TFLl6utGK9NrZ4457QpMSlNt18d9445I0fIQnFmBAC744x8A7MIJLiJAE944xGHXOrzB4PAAx45pHVbG29K3F8n145pHpLIpTHZ58A745pOfDO1j53v8d945pPrF3jl91FNll46P76nLFHPrF8A746hEzh9VjE9jNhz489Ezh6ubGjPNhz49b3Y9CrJMCnNhz49bCA3ILZNBT8d94FhGzNChRODL8Jz4I1H7n8nJATpPmt4IbCQ1AC7Fr7Nhz4ItHVbGI7K3F8Jz4ItOAjA1fJoR8A74LD36ZPrF9SpNhz4MNDSBA1xK4hIYd4O7JW94LDEWNNhz4O7JW9EjR3yZNrZ4PHDfFH4tNAJ8A74PHNjRF0rF9r8AP4PHOGXEUvDat9iD4SlH4tKzJIyB4yh4SlKBxGYxMIJ2xr4WXDjtJuX9kFIYd4WXIK7FK1Jg18d94WXIa5Eo5Jvz8d94WXIgBEI9KLp8d94WXNXFEo5DR1AAx4WXNt1Eo5Ed38d94XzC8J9XTLhRIYd4YZH4tKyRIpT52T4ZRIK795tOpN9f14ZRIaxA7lNWf9f14aJAGTLQbM2L8A74aJMPrHJ7JCh2xr4bBMPrHJ73b3IYd4ijJuXH4tLnp2xr4ld7GfEsRFr7Nhz4ldKaLBPJKvX8n14r94yhAYBMEFNrZ4r955fB1DLnpNhz4r9JN9HZ567pIYd4sJCFZLnpO433U54yzGovCeFNrZ8A752TNXFEo5DR19f153vD6hO9HJ8L51b55N5cBO7XLQbAE955NG4TO7XAyJAE955NGWdO7XCZt8AP577MPrGnB3b3IYd5BB8ElKNZE7hIYd5BBGovEP7BVzIYd"},
{23,3,"8A7F7FE2BIyBAC78ETCaBOIZGK952T8ETMUDGWdEC352T8GnGQXH4bEzh9iD8GnIXBH4tCQ1AAx8GnIXBHapCQ19f18GnP3b45p3GjPmt8HfLzj4XzLzR9f18IF58Z9xJJNjNhz8IF9LZGWdBj3KaL8JhFSjBmXCMFIYd8JzA9nHXd6arNrZ8JzNS1BfHI3r4yh8OvMYZ67p8oBKaL8Q5HfBFmBK5r4WX8Q5I3r78XOXf8Jh8Q5I3rHXdE8Z8Jh8VJBO9Oc1Gzf4yh8VJEsRJ9nDi9AE98d9CrJ8g3G5vKDP8d9MEFFRHH4b36Z8g3BR3KNZGK99f18g3PrFBIvCMp8Gn8gL4qHO43K698n18kP7dbIa5LGjAF18kPCaBOIZGK94WX8kPMEFI2PEUv2xr8kPOqpCpHBmX8Gn8khCm5DxpMiR8Gn8khOAjHWB7P58d98mjLFHCeFE8Z9f18n1ILZChRI0f8d98n1KvFChRFQz8d98nb4hHOpNJMr8mj8nbAo9MYZJH352T8oB9LZG0hBj3KaL8oB9Lr7dbM7ZIYd8oBDNpPrFAGT8A78oBEY7Ao9Bj3KaL8oBGP5FFfHNl8d98oBL5hFFfBfH9f18oBNAJECvC1d8Gn8uZMIJBQlDe5AC78uZOrzBQlB4PAC78uZP5LHVb6ed8Jh8wJOarDi9EC352T8xTEjRIN1JN952l8xTFQz8IFNY7AF18xTI0f8IFKyRAF18xTIh3I2PB7t9f18xTO9HH0X6hX9f18xlM2d79hJX18mj91FEsRIdrDi9AE991FF0r4aJE8ZNir91FJrL8kh8d9KDP91FMR18kh63TKDP91FPMl4aJ3mfNir91FPrF3oP445Nir92h53vCalG0hNll92h8nbAF1EgXNhz92hA1xHU963TNrZ92hK7bGY5Byj8mj92zK7bGY5Cal8AP92zPGxGY57RP8AP95t4FhHXdBj3NrZ95t66NHapPWd8A795tBVhBvF8A7Pmt95tIXBFQz4r9IYd995CQ1HapIXB8mj9ApHsFAYBK5r8mj9Dj53LKwzMSl8n19DjOQh4KvPWd2xr9DjOpNAb5GnB52T9FBBO9PWdHDJ36Z9Fl3ZtKzJMTvAAx9Fl8g3KzJHNlAAx9G3ILZChRI0f8A79G3KvFChRFQz8A79G3Lt3A4Z6XxIiD9If4yhGFnBVzOQh9If76nG2jPrF8AP9IfCG9G2jKht8AP9IfG2jGovE8ZAAx9IfHWBG29Eq78mj9IfK5rG29CGR8mj9LZF9rJNjEJt8Gn9RN9bXFnd5qPPmt9V9HkzLeF9Fl8Jh9VjG5vH4bE8Z9f19VjHkzO436pN8Jh9VjHmRDyPGwT8Gn9XB3WzIdrOXfAE99XBDNpJvzEzh8d99XBEs9J9DE8Z8mj9XBG0hFFfHWB8A79YvK7bG29Cal8AP9YvNllBvFBVh9iD9YvPGxG297RP8AP9a59Lr6rhM7ZIYd9a5HmRDat6oDIiD9a5L5hETlBfH9f19bXHkzDfFHBH8Gn9bXNjR52l4O7Nhz9f1Jg1EI9IK74WX9f1PmtB2xBfH8Jh9kF4PHGzfBT5NrZ9kF82HJivNzh4yh9kF9YvGzNBT5IiD9kFDEpEWNNzh4yh9l7Av7O1jGkH51b9n930lIu7OarAAx9n933xIu7OXfAAx9n9AuFCaB9UHNhz9n9CKDJ9nM8j33x9n9Es9ItFE8Z8mj9n9HTZJ9nGzN33x9n9MPrDwfBXR8mj9n9MPrJ9D6Kt8mj9vrLTn5BBLFr8d99wRHNlETlGP58Gn9wRP5LGTj6ed8Jh9wj6qp7ArNnDIiD9xJBdpCMFDoFIiD9yBEGhDSBOGF4WX9yBLiJDi9G2j52TA0D82HJSxNzh4yhA0D8HfJvzK5r8A7A0DDEpEGPNzh4yhA1f8HfKzJHWB9f1A1fG0hKzJ9n99f1A1fJrLG29CEz8JhA1xLeF92h72jIiDA3P30lOrzJuX8d9A3P4FhGnBBVzNrZA3PCUf5yXDfFOHzA4ZAiLMUDK6936ZA4ZJrLG29CEz8GnAAxCQ1H4tIXB8GnAAxG7NO215yXAAxACh58ZIK7OXf8GnAGBAF18xlD9JNrZAGBMTv6B13GjOHzAGT2jLNtJOZ751bAGT7u9IQnOqp51bAGTFdBIQnH7n51bAJ58BZHmRBe7IYdAJ58WlI2PB2xIYdAJ5CKD9DjFubIiDAJ5CKDIdrM8j33xAJ5HTZIdrGzN33xAJ5K3F9Dj8BZIiDAJ5MCn6qp3FZNrZ"},
{23,4,"Ar3AF1J8LLCx52TAr3AHvMxFE3v8JhAr3CrbMxFBUF8JhAr3MeN9G3IXB5BBAr3OiPI3r4WX8JzAv7CW74IbF19NirAyJA3PGI7O7X52TAyJK3FJeHAcp5BBAyb7ODH4tMiR8JhB2x75LMVfH398mjB6RCMp7d1BVzNrZB6RO1jBe7Efx51bB7JBpjJLPJCh4yhB7JJhT9SpHZ58d9B7t3oPPmt7C1IYdB7t7DT52lJNjNhzB7tAYTKADEP7AE9B9L66NNnDFClAE9B9L7C1B4PGTjKaLB9L9kFNXFCKn9iDB9LCrb8BZE3vKDPB9LK7bB4P3Y9KaLB9LKrBHZ56g5AE9B9LNXFCQ1EOX4yhB9LNXFHZ5401AE9BIvHapGzNCJv8GnBIvNAJ8xTEGP8mjBMh7LJ4KvJZLNrZBMh9G3GzNPl936ZBO951bJ8L79zNllBPJKYt8khHU98GnBPJNS1BO9FFf4yhBQl72jLxzHM18gLBQlC1d58ZDatOHzBUF4r9NoxL8J5BBBVz7MlLjlHXd8JhBVzEI9B71OWD52TBXR7a7LxPH4t8JzBZT3mfPIP7GfIYdBdp7ZpAdPGY5K4hBe78xTB9LE8ZKaLBe7ILZBvF3yZKaLBfHCQ176nBVzNllBfHFmBHpLCZt8d9Bn7CrJLxzBXR8JzBpj7u9JSxMFP51bBpjFdBJSxEWN51bBvF66NNXFFCl9iDBvFCQ16qpBVzNllBvFKrBGnB6g5AE9BvFNXFGnB401AE9C8J6HzMFPH7n8gLC8J91FMFPEOX8gLC8JAdPMVfBXR9f1C8JD6hBe7OZ751bCGRFK18g36UTNirCHtPmt5btEWN8GnCJvAF1KyRE9j8mjCJvKadB2x3o7IiDCKD3mf9FlMYZIYdCKn75LLjlH398GnCKnKc58BZH4b8GnCMpK69Di9BVh8n1CZtMTv3pr3IBOHzCaB4YZILZ7GfNirCeF6HzMFPH7n8APCeF91FMFPEOX8APCeFAF1KwzEMn8GnCfzJN9IbpCkv33xCoPKad5cB8kPIiDCrJ6hXJZL3U5NrZCrb5qPGa7MYZ8d9Crb7u9LGjEGPAAxCuD49bIK75J1PmtCuDEP76hXOIZ8APCuDOzFFnd3zj8n1CxP6IHM2LGP58mj"},
{25,5,"DJlCxPByj4MNNrZDLDCA3DwfLzR52TDNp7mbK3F6XxIiDDNpAMHK3F3yHIiDDNpPrF8etAGB8JhDQ99Vj6vTG29KaLDQ9Fr7Oar7a751bDQ9OiPA7l9tX8JzDQ9P3b6vTCkv8JhDRb7jh7MlEA1NllDRbAGB6r7HCjIiDDRbJ8d4KvJNjAAxDRbM8j70h3o7K4hDSBJuX3WzOXf52TDWFAYBEC3I2PAAxDWFD7rJObAGBAAxDWFFubEC3CfzAAxDatAGTG0hLZJ52TDhZAYBLjlFSj51bDhZJ8d44xJNjAAxDhr7Tj6XxF2JNhzDhrHBHCcn4FhIiDDjt6TtG0hK3FAC7DjtLvxG0h4bBAC7Dr9577GjPLzR8mjDxpFubBe7EmLAAxDxpHBHCMp4FhIiDDyPCGRLFH8khAF1E0jB1DMVfAJ58d9E0jDatMVf7jP8d9E0jE3vLZJ6arAF1E2B3GjDQ9PZpAAxE5f7ODGYxKAD8GnE5fB71KzJF6f5BBE7hCQ13IBGQXKDPE8ZECv9G38etKDPE9j53vD7rNtJAF1E9j5774hZNnDIiDEC3GLt7BR8A7KaLEC3IpTGY5Bj35BBECL4Fh7C1M7ZIiDECL6qpAdPECvKaLECLB7tEUvGwT9iDECLO7X5h7Ckd9iDECvLt3G0h489AF1EGP4MNK3F45pNhzEGP577E3v9ApNrZEGh5J1H39Jg1AAxEGhFubCslFFf8A7EI9BpjOX5Ckv33xEMn445EzhOGF8n1EOXBaL9V9Av7K4hEP7Dat8WlJivAE9EP7FRH8g39FBIiDEP7GQX7FD8BZKDPETlDEpLzR6arAAxEUv5A1E8Z8xTNirEUv6arBMhDnxKDPEUvB6R9l7AX1KaLEUvCrJB2x3mfOHzEUvD7rLiJ7Tj9f1EWN6UTFOx6IHNllEWND7rHpLI2P2xrEWNNoxCslCHt2xrEY7FubDg7Cfz9f1EY7GHXDg7Bn7AAxEY7GHXEC3Bn79f1EY7LiJC8JF7F2xrEd39XTLCfGa74WXEd3Ar3NHZ9RN8GnEd3Ltv67pIdr5BBEfx3sBOzFJpt36ZEgX8BZG4TMYZ4yhEgXG7NCslEd38A7EgXNnDG4T6wv4yhEgXOGX6hXB719iDEhzDatOqpAMH2xrEhzDe5OqpAJ52xrEhzHWBGI79dZ8JzEjRHV1DwfBVh8n1EmLDLDPbH9n92xrEmLDR1JN9AGB8d9Eo52jLFTtOpN8d9Eo53GjEC3PZp8d9ErHI0fLS33pr8JzErHMVfGVl3oP8mjEs93Y9H4tMoX8A7Es967pH4tKEr8A7Es9DWF8mjJ7lAAxEs9DWF9IfJ7l9f1Es9MSl6cJ3oPIiDEsR4FhJeH3prNrZEzhB1DDwfHjX8mjF0rM8RAcpDfF52TF8zJuX3VFJbN8JhF9r6oDMFP3Y9IiDF9r7LJ5yXDi9OHzFClDxpOc19jN2xrFClJW9IQn53L8GnFFN577IEJ41TNrZFFNBUFG1H3VXKDPFFfBUFLCfAGT8GnFFfBj3M2L9Bz8GnFPX3qRGWdATpKDPFPX4LDDwfNzh8mjFPX5cBHsFOc12xrFPXAiLF2JLpZ3U5FPXAybF2JLZJ3U5FPXB7t7TjOIZ8A7FPXGWdB7tFFN8APFQz489DF7NTTAC7FQzAiLMEFEzh36ZFRHG7NDfFCcn8d9FSj2xrG4TLnpAAxFSjDWFMFP75L8A7FVdFubBe7EmL8d9"},
{25,8,"L9B5btCcnHNl9iDLFHG5v6edCJ3AAxLMp6UlFTtIbp4WXLMp9YvBIvJCh52TLMpEjRFQz6cb8JzLNh8khLS35BB9iDLQbA0D6pf3mfOQhLQbIgl9G37RP9f1LS335P6edP3bAE9LS372RCfzGzN8JzLS37FDAb5GzNAC7LS3G7N6edC1dAE9LTn6Tt55N9f1NllLZJA0D6pf3mfOHzLeF7C1P293oP8n1LeFGaP8etEP75BBLhRAcpFFf8etAF1LhRDTv8khHV152lLhRMOz6ut78X8JzLiJ6qp4Xz9V9NrZLiJ8g3LpH445AC7LiJ995MFP53L8JhLiJIQnAJ57LJ8gLLjlAerEhz9f19iDLnpGipCJv6wv8gLLnpOWD4Xz7RP8APLpZ3Y972RAC7NrZLv57FD3yH8uZOQhLv5EI9Ab5F8z4WXLvxG0h45pJOb52lLxz94RLCf3zjAF1LxzAC7Lvx46z8GnLxzBQlEgXAE98APLzR7ynFTtHXd3U5M2L6HzPMl3zj8n1M2L9lzLeF4hH8JzM2LECLDfF6KtAF1MCn8A7CeF3FHKDPMEFBT57jPGjP8JhMFPBVhJeH4kT8JzMOz4LDFizIyB52TMPr76n2xrA7lNrZMR130lHpLKEr2xrMR15btCslHNl8APMR18mj6TtIa5AC7MR1AYTCslBvF8gLMR1GVl6TtAr3AC7MTvBO9EgXErH33xMTvCA3IK74ij8n1MUD8g3L3N445AC7MiR5cBA1xJU78d9MiR83jCeFJZL3U5MiRG1H4sJJNj3U5MiRIdr9V96pf8mjMiRIdr9Vj6vT8gLMiRJOb9FB6qp8GnMwx8mj5xxIa5AC7MwxECLAb5ECv4WXMwxGVl5xxAr3AC7NBTOmT3Gj6vT8JhNCv9Ix5btJZL8mj"},
{25,9,"Nhz6ut9SpLCx5BBNjR5BB621NDD8JzNjRJSx4bBE9j4WXNjRJnH6rhAuF5BBNjROpN4bB8nJ4WXNkJ489DwfJcF52TNkJ52l7Zp5gFOQhNkJLTn6ub46zAE9Nll2qbBZTI3rAE9Nll7mb60Z53LNrZNnD6Ul8kPMOz52TNox3zj7RzMtT8JhNoxBAnA1fCm58gLNoxFr78zn7ZpAE9NrZ6g5J7l6cJAC7NzP52lA9nIyB8JhNzP6CBKc57MB8JzNzPBAn76nDxpAF1NzPEUv53vE8Z8n1O1j9If7BRHAz8n1O7X6En7LJ2zJPmtO7XIkX55NF2J3U5O9HBe76b9FOx8gLOAj3yHJeH9tX8n1OHzDatDi9AMH4WXOWD6OfMiR9mZ33xOWDLTn6ed46z9iDOXf2p9BZTHpL9iDOXf3FH55NOvB8gLOZ73NP4dDNhzAC7OZ7Be779hEJt8n1Oc16arJMr7a78JzOc1LMp6En445AC7Okj9If6vTHAz8JzOkjB7t8znBtD9iDOqp8Ov8WlJW95BBP29G4TBtD8xT4WXP3b3bvLxzCMF3U5P3b6EnLxz9jN3U5P3bBO9Lxz4a13U5PGx5yXIMR79h9iDPY53FH7db5cBOQhPbH5yXLDXACP3U5"},
};
int main(){
ios\_base::sync\_with\_stdio(0);
//freopen("input.txt","r",stdin);
//freopen("output.txt","w+",stdout);
pre();
int test;
scanf("%d",&test);
while(test--){
scanf("%d%d",&sum,&tl);
// printf("\\n%d %d\\n",sum,tl)a
bool fin=false;
for(int i=0;fpre\[i\].pref;i++){
if(fpre\[i\].s==sum&&fpre\[i\].t==tl){
fin=true;
decode(fpre\[i\].pref);
// printf("%d %d\\n",fpre\[i\].s,fpre\[i\].t);
//printf("%d %d\\n",sum,tl);
break;
}
}
Set(mz,0);
if(!fin)solve();
if(test)Pln();
}
}