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

struct Node{
    string s;
    int steps;
};
map<string,int> vis;

int BFS(string s){
    queue<Node>q;
    vis[s] = 1;
    q.push({s,0});

    while(!q.empty()){
        Node now = q.front();
        q.pop();

        if(now.s.find("2012") != std::string::npos){
            return now.steps;
        }

        for(int i = 0; i < now.s.size() - 1; i++){
            Node next;
            string str = now.s;
            swap(str[i],str[i+1]);
            next.s = str;

            if(vis[next.s])
              &...