#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

typedef pair<int,int> pii;
#define fi first
#define se second
#define mk make_pair

#define max(x,y) ((x)>(y)?(x):(y))
#define re register

const int MAX=int(1e6)+1;

int mat[MAX];

struct SAM{
	
	struct node{
		int link,len;
		int nxt[2];
	}t[MAX];
	
	int tot;
	SAM() {tot=1;}
	~SAM() {;}
	
	inline int insert(int ch,int last,int len){
		int cur=++tot,p=last;
		t[cur].len=len;
		for(;p&&!t[p].nxt[ch];p=t[p].link) {
			t[p].nxt[ch]=cur;
		}
		if(!p) {
			t[cur].link=1;
		}
		else {
			int q=t[p].nxt[ch];
			if(t[p].len+1==t[q].len){
				t[cur].link=q;
			}
			else {
				int clone=++tot;
				t[clone]=t[q];
				t[clone].len=t[p].len+1;
				for(;p&&t[p].nxt[ch]==q;p=t[p].link){
					t[p].nxt[ch]=clone;
				}
				t[cur].link=t[q].link=clone; 
			}
		}
		return cur;
	}
	
	void get(char *s){
		re int p=1,l=0;
		int len=strlen(s+1);
		for(re int i=1;i<=len;i++){
			int ch=s[i]-'0';
			if(t[p].nxt[ch]) p=t[p].nxt[ch],l++;
			else {
				for(;p&&!t[p].nxt[ch];p=t[p].link);
				if(p) l=t[p].len+1,p=t[p].nxt[ch];
				else p=1,l=0;
			}
			mat[i]=l;
//			cout<<i<<" "<<l<<"\n";
		}
	}
	
}S;

struct Trie{
	
	struct node{
		int nxt[2];
	}t[MAX];
	
	int tot;
	
	Trie() {tot=0;}
	~Trie() {;}
	
	void insert(char *s){
		int len=strlen(s+1),u=0;
		for(re int v=s[1]-'0',i=1;i<=len;i++,v=s[i]-'0'){
			if(!t[u].nxt[v]) t[u].nxt[v]=++tot;
			u=t[u].nxt[v];
		}
	}
	
}Tr;

struct qaq{
	int body[MAX];
	int hed,tail;
	
	qaq() {hed=1,tail=0;}
	~qaq() {;}
	
	void push(int x) {body[++tail]=x;}	
	int front() {return body[hed];}
	void pop() {hed++;}
	bool empty() {return hed>tail;}
	
}q;

int dp[MAX],que[MAX];
int n,m,pos[MAX],hed,tail;
char s[MAX];

void bfs(int s){
	q.push(s);
	pos[s]=1;
	while(!q.empty()){
		int u=q.front();q.pop();
		if(Tr.t[u].nxt[0]){
			pos[Tr.t[u].nxt[0]]=S.insert(0,pos[u],0);
			q.push(Tr.t[u].nxt[0]);
		}
		if(Tr.t[u].nxt[1]){
			pos[Tr.t[u].nxt[1]]=S.insert(1,pos[u],0);
			q.push(Tr.t[u].nxt[1]);
		}
	}
}

bool check(int L,int len){
	memset(dp,0,sizeof(dp));
	memset(que,0,sizeof(que));
	tail=0;hed=1;
	for(re int i=L;i<=len;i++){
		dp[i]=dp[i-1];
		while(hed<=tail&&dp[que[tail]]-que[tail]<=dp[i-L]-(i-L)) tail--;
		que[++tail]=i-L;
		if(hed<=tail&&que[hed]<i-mat[i]) hed++;
		if(hed<=tail) dp[i]=max(dp[i],dp[que[hed]]+i-que[hed]);
//		cout<<i<<" "<<dp[i]<<"\n";
	}
//	cout<<"\n";
	return dp[len]*10>=len*9;
}	

void solve(char *s){
	int len=strlen(s+1);
//	for(int i=1;i<=len;i++) cout<<i<<" "<<mat[i]<<"\n";
	re int l=1,r=len;
	int ans=0;
	while(l<=r){
		int mid=l+r>>1;
		if(check(mid,len)){
			l=mid+1,ans=mid;
		}
		else r=mid-1;
	}
	cout<<ans<<"\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	
	cin>>n>>m;
	for(re int i=1;i<=m;i++){
		cin>>(s+1);
		Tr.insert(s);
	}
	bfs(0);
	
	while(n--){
		cin>>(s+1);
		S.get(s);
		solve(s);
	}
	
	return 0;
}