#include<bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
int n;
int t,s;
struct node{
	int value;
	int deep;
};
map<int,bool>a,f;
string to_string(int n){
	int p=log10(n);
	string s;
	for(int i=p-1;i>=0;i--,n/=10){
		s[i]=n%10;
	}return s;
}
int stoi(string s){
	int n=0;
	for(int i=0;i<s.length();i++){
		n*=10;
		n+=s[i]-'0';
	}return n;
}
int f1(int n,int i,int j){
	string s=to_string(n);
	swap(s[i],s[j]);
	return stoi(s);
}
int f2(int n,int i){
	string s=to_string(n);
	s.erase(i,1);
	return stoi(s);
}
int f3(int n,int i){
	string s=to_string(n);
	return s[i]-'0';
}
int f4(int n,int i,int v){
	string s=to_string(n),str;
	char c=v+'0';
	s.insert(i+1,str);
	return stoi(s);
}
void bfs(int s){
	queue<node>q;
	a.clear(); 
	q.push({s,0});
	while(!q.empty()){
		node last=q.front();
		q.pop();
		if(f[last.value]){
			continue;
		}a[last.value]=true;
		if(last.value==n){
			cout<<last.deep<<"\n";
			return ;
		}int p=log10(last.value);
		//条件1 
		for(int i=0;i<p;i++){
			for(int j=i+1;j<p;j++){
				int x=f1(last.value,i,j);
				if(!a[x]){
					q.push({x,last.deep+1});
					a[x]=true;
				}
			}
		}
		//条件2
		for(int i=0;i<p;i++){
			int x=f2(last.value,i);
			if(!a[x]){
				q.push({x,last.deep+1});
				a[x]=true;
			}
		}
		//条件3 
		for(int i=1;i<p-1;i++){
			for(int j=f3(s,i)+1;j<=f3(s,i+1);j++){
				int x=f4(s,i,j);
				if(!a[x]){
					q.push({x,last.deep+1});
					a[x]=true;
				}
			}
		}
	}f[s]=true;
	cout<<-1<<"\n";
}
signed main(){
	cin>>n>>t;
	while(t--){
		cin>>s;
		bfs(s);
	}
	return 0;
}

terminate called after throwing an instance of 'std::out_of_range' what(): basic_string::erase: __pos (which is 1) > this->size() (which is 0)