#include <bits/stdc++.h>
#define pb emplace_back
#define fir first
#define sec second
using pii = std::pair<int,int>;

const int maxn = 21;

int n,cnt;
char s[maxn],t[maxn];
std::map<pii,bool> mp;
std::queue<std::tuple<int,int,int> > q;

int Next(int x) {
	return (x << 1) | (x >> (n - 1) & 1);
}

void work() {
	scanf("%s %s",s,t);
	int S = 0,T = 0;
	for(int i = 0;i < n;++ i)
		S |= (s[i] ^ '0') << i;
	for(int i = 0;i < n;++ i)
		T |= (t[i] ^ '0') << i;
	while(!q.empty())
		q.pop();
	q.emplace(S , T , 0);
	mp.clear();
	while(!q.empty()) {
		auto [x , y , z] = q.front();
		if(!x)
			return printf("%d\n",z),void();
		q.pop();
		for(int i = 0;i < n;++ i) {
			int p = y ^ (1 << i);
			x ^= p;
			p = Next(p);
			if(mp[{x , p}])
				continue ;
			mp[{x , p}] = true;
			q.emplace(x , p , z + 1);
		}
	}
	return ;
}

int main() {
	freopen("lightoffg.in","r",stdin);
	freopen("lightoffg.out","w",stdout);
	int T;
	scanf("%d %d",&T,&n);
	while(T --)
		work();
	return 0;
}