algospot - clocksync

//algospot - clocksync
 
#include <iostream>
#include <vector>
using namespace std;
 
#define INF 33333
 
int arr[16];
 
int big(int x, int y)
{
    return x > y ? x : y;
}
 
vector<vector<int> > button({
    vector<int>( { 0, 1, 2 }),
    vector<int>( { 3, 7, 9, 11 }),
    vector<int>( { 4, 10, 14, 15 }),
    vector<int>( { 0, 4, 5, 6, 7 }),
    vector<int>( { 6, 7, 8, 10, 12 }),
    vector<int>( { 0, 2, 14, 15 }),
    vector<int>( { 3, 14, 15 }),
    vector<int>( { 4, 5, 7, 14, 15 }),
    vector<int>( { 1, 2, 3, 4, 5 }),
    vector<int>( { 3, 4, 5, 9, 13 })
});
 
void init()
{
    int u;
    for(int i =0; i<16; i++)
    {
        cin >> u;
        arr[i] = (u/3) % 4;
    }
}
 
bool isEnd()
{
    int ret = 0;
    for(int i = 0; i<16; i++)
        ret += arr[i];
    if(!ret)
        return true;
    return false;
}
 
int bf(int idx, int num)
{
    if(isEnd())
        return 0;
    else if(idx == 10)
        return INF;
 
    int ret = INF;
    int copy[16];
 
    for(int i = 0; i<16; i++)
        copy[i] = arr[i];
    for(int i = 0; i<button[idx].size(); i++)
        arr[button[idx][i]] = (arr[button[idx][i]]+num)%4;
 
    for(int i = 0; i<4; i++)
        ret = min(ret, bf(idx+1, i));
 
    for(int i = 0; i<16; i++)
        arr[i] = copy[i];
    return ret + num;
}
 
int bfAll()
{
    int ret = bf(0, 0);
    for(int i = 1; i<4; i++)
        ret = min(ret, bf(0, i));
    return ret;
}
 
int main()
{
    int C; cin >> C;
    for(int t_num = 0; t_num < C; ++t_num)
    {
        init();
        int ans = bfAll();
        if(ans == INF)
            cout << -1 << endl;
        else
            cout << ans << endl;
    }
}