//生成的数字不能有0 
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
bool vis[MAXN];
int s,n,now[MAXN],step[MAXN];//now为当前存储处理的数的数组 
int change(int a[],int len){//将数字由数组形式变为整数形式 
	int sum = 0;
	int b[1000];
	for(int i = 1; i <= len; i++){
		b[i] = a[len - i + 1];
	}
	for(int i = 1; i <= len; i++){
		if(a[i] != -1){
			sum *= 10;
			sum += a[i];
		}
	}
	return sum;
}
void get(int a[],int num){//将数字由整数形式进行拆分 
	int now,b[1000],len = 0;
	while(num != 0){
		now = num % 10;
		num /= 10;
		len++;
		b[len] = now;
	}
	for(int i = 1; i <= len; i++){
		a[len - i + 1] = b[i];
	}
}
int g(int num){//求该数的位数 
	int len = 0;
	while(num != 0){
		num /= 10;
		len++;
	}
	return len;
}
int main(){
	queue<int> q;
	cin >> s >> n;
	q.push(s);
	memset(step,0x3f,sizeof step);
	int lenmax = g(s);
	step[s] = 0;
	vis[s] = 1;
	while(!q.empty()){
		memset(now,-1,sizeof now);
		int num = q.front();
		q.pop();
		get(now,num);
		int next,x,len = g(num);
		for(int i = 1; i <= len; i++){
			x = now[i];
			now[i] = -1;//进行删除一个数的操作 
			next = change(now,len);
			now[i] = x;
			if(g(next) != 0){
				if(!vis[next])q.push(next);
				vis[next] = 1;
				step[next] = min(step[next],step[num] + 1);
			}
		}
		for(int i = 1; i <= len; i++){//进行交换两个数的操作 
			for(int j = i + 1; j <= len; j++){
				swap(now[i],now[j]);
				next = change(now,len);
				swap(now[i],now[j]);
				if(!vis[next])q.push(next);
				vis[next] = 1;
				step[next] = min(step[next],step[num] + 1);
			}
		}
		int b[1000];//进行添加一个数的操作 
		memset(b,-1,sizeof b);
		for(int i = 1; i <= len; i++){//先将原数 转移到另一个数组 
			b[i] = now[i];
		}
		int cnt = 1;
		for(int i = 1; i <= 2 * len; i++){//每两个数之间留空，方便插入 
			if(i % 2 == 1){
				now[i] = b[cnt++];
			}
			else{
				now[i] = -1;
			} 
		}
		for(int i = 2; i < 2 * len; i++){
			if(now[i] == -1 && len + 1 <= lenmax){//满足长度不超过原数长度 
				for(int j = now[i - 1] + 1; j < now[i + 1]; j++){
					now[i] = j;
					next = change(now,2 * n + 2);
					if(!vis[next])q.push(next);
					vis[next] = 1;
					step[next] = min(step[next],step[num] + 1);
				}
			}
		} 
	}
	int que;
	while(n--){
		cin >> que;
		if(step[que] > 100000){
			printf("-1\n");
		}
		else printf("%d\n",step[que]);
	}
}