#include
#include
#include
#include
using namespace std;
struct node
{
int x, y, dir, step, g;
friend bool operator < (node a, node b)
{
return a.step<b.step;
}
};
int dd[][2]={0, 0, -1, 0, 0, 1, 1, 0, 0, -1};//左上右下
int map[22][22];
int vis[22][22][2];
int xx, yy, n, tt;
int inmap(int x, int y)
{
if(x>=0 && x=0 && y<n)
return 1;
return 0;
}
int bfs()
{
int i;
memset(vis, 0, sizeof(vis));
priority_queue q;
node now;
now.x=0;
now.y=0;
now.dir=3;
now.step=0;
now.g=0;
q.push(now);
vis[now.x][now.y][0]=1;
while (!q.empty())
{
now=q.top();
q.pop();
if(now.x==0 && now.y==0 && now.g==1)
{
return now.step-10;
}
for(i=1;i<=4;i++)
{
node temp;
temp.step=now.step;
temp.g=now.g;
temp.x=now.x+dd[i][0];
temp.y=now.y+dd[i][1];
if(inmap(temp.x, temp.y) && !map[temp.x][temp.y] && !vis[temp.x][temp.y][temp.g])
{
if(i!=now.dir)
{
if(i%2==1)
{
if(now.dir%2==1)
temp.step-=20;
else
temp.step-=10;
}
else
{
if(now.dir%2==1)
temp.step-=10;
else
temp.step-=20;
}
}
if(temp.x==xx && temp.y==yy && temp.g==0)
{
temp.g=1;
temp.step+=990;
}
vis[temp.x][temp.y][temp.g]=1;
temp.step-=10;
temp.dir=i;
q.push(temp);
}
}
}
return -1;
}
int main()
{
int k;
int a, x, y;
scanf("%d", &k);
while (k--)
{
scanf("%d", &n);
memset(map, 0, sizeof(map));
while (scanf("%d%d%d", &a, &x, &y))
{
if(a==-1 && x==-1 && y==-1)
break;
if(a==1 || a==2)
map[x][y]=1;
else if(a==3)
{
xx=x;
yy=y;
}
}
if(map[0][0]==1)
{
printf("-1\n");
continue;
}
int flag=bfs();
if(flag==-1)
{
printf("-1\n");
continue;
}
int ans=flag;
if(ans<=0)
ans=-1;
printf("%d\n", ans);
}
return 0;
}
