/*
讲符合要求的子序列 从两端缩短 ，得到最小值
*/
#include
#include #include using namespace std; int vis[1000001]; int f[1000001]; int n,m,k; int init() { memset(f,0,sizeof(f)); } int main() { init(); int t,count=1; scanf("%d",&t); while(t--) { memset(vis,0,sizeof(vis)); scanf("%d%d%d",&n,&m,&k); if(k<=3) { printf("Case %d: %d\n",count++,k); continue; } for(int i = 0; i<=3; i++) f[i] = i; vis[1] = vis[2] = vis[3] = 1; int ans=0,res=3,mp=11000000; for(int l=1,r=4; r<=n; r++) { f[r] = (f[r-1]+f[r-2]+f[r-3])%m+1; if(!vis[f[r]]) { vis[f[r]]=1; if(f[r]>=1&&f[r]<=k) res++; } else { vis[f[r]]++; } if(res==k) { mp = min(mp,r-l+1); } while(l<=r) { if(f[l]>=1&&f[l]<=k&&vis[f[l]]==1) break; vis[f[l]]--; l++; if(res==k) { mp = min(mp,r-l+1); } } } if(mp!=11000000) printf("Case %d: %d\n",count++,mp); else printf("Case %d: sequence nai\n",count++); } return 0; }