Problem: Description

KULASIS is the name of a system developed and operated by the Higher Education Research and Development Promotion Organization for the purpose of providing information on common subjects throughout the university on the Web, supporting students and faculty members, and improving services. KULASIS started with the development of the online syllabus in 2003, and has gradually expanded the system to include Web bulletin boards, course registration, grades (scoring registration, scoring confirmation from students).
Students can use functions such as confirmation of academic affairs information (class cancellations, class changes, reports), course registration, and scoring confirmation from both inside and outside the university from a personal computer or mobile phone. The number of logins exceeds 10,000 on many days, and it has become widespread as an academic affairs information system at Kyoto University, and is indispensable for taking common courses throughout the university. We are developing this KULASIS so that it can be applied not only to common subjects throughout the university, but also to undergraduate specialized courses and graduate schools.
http://www.z.k.kyoto-u.ac.jp/introduction_kulasis.html

Q, a student at Kyoto University, was logged in to KULASIS to form a late syllabus. When I was wondering which subject I was going to enter, KULASIS suddenly gave off a dazzling light and moved to another page.
The page to which the transition was made was as shown in the figure below. The subject name and evaluation (impossible, acceptable, good, excellent) are written in the 5x5 square, and 16 ● buttons are arranged on the grid.
It was Q that I did not know what happened, but apparently when I press the ● button on the grid, the evaluation of the subjects in the upper right, lower right, upper left, and lower left is not possible → Yes, Yes → Good, Good → Excellent, Excellent → Impossible.


<image>


You can press the ● button as many times as you like.
I'm not sure if KULASIS has been rewritten by someone or if I'm dreaming, but if I can confirm my grades with this, Q wanted to get as good a grade as possible.
Confident that he was collecting a lot of credits, Q decided to maximize his fighting power in preparation for his assignment to the laboratory six months later than the number of credits itself.
Combat power is the total value of the evaluation of each subject converted into impossible → 0 points, acceptable → 60 points, good → 70 points, excellent → 80 points. It is thought (in the Q department) to show how superior it is.

Now that the subjects displayed on the KULASIS screen and their evaluations are given, please describe the program that outputs the maximum value of the combat power that can be obtained.



Input

The number of test cases is given on the first line of input. The number of test cases is guaranteed to be 100 or less.
From the second line onward, 5x5 numbers are lined up, and the evaluation of the subject displayed on the KULASIS screen is given, and 1,2,3,4 correspond to impossible, acceptable, good, and excellent, respectively.
If it is 0, no subject is registered in that frame.
The test cases are separated by a blank line.

Output

Output the maximum value of combat power that can be obtained for each test case.

Example

Input

5

1 1 0 3 3
1 1 0 3 3
0 0 0 0 0
2 2 0 4 4
2 2 0 4 4

1 1 1 0 0
1 1 1 1 0
1 0 1 1 0
0 0 1 1 1
1 1 1 1 1

0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

4 3 4 3 4
3 4 3 4 3
4 3 4 3 4
3 4 3 4 3
4 3 4 3 4

2 2 2 2 2
0 0 0 2 0
2 2 0 2 0
2 2 0 2 0
0 0 0 2 0


Output

1280
1420
0
1920
1020

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int field[6][6];
int dp[6][6][1<<12];
int n;
const int INF=1000000000;
int seiseki[4];

// óÔsÌidxÔÚÌlðæèo·
int getValue(int s,int idx){
    int b1=((s>>idx*2)&1);
    int b2=((s>>idx*2+1)&1);
    return b1+2*b2;
}
// óÔsÌidxÔÚÉlxðZbg
void setValue(int &s,int idx,int x){
    int b1=((x>>0)&1);
    int b2=((x>>1)&1);
    if(b1==0)
        s&=~(1<<idx*2);
    else
        s|=(1<<idx*2);
    if(b2==0)
        s&=~(1<<(idx*2+1));
    else
        s|=(1<<(idx*2+1));
}

// (»Ýn_ÌxÀW,»Ýn_ÌyÀW,êÔµ½5}XÌóÔ
int rec(int x,int y,int s){
    if(x==4){
        x=0;
        y++;
        if(y==4){
            int res=0;
            // ¡ÌsÌlð0-4Ìn_ÌàÌð·×Ä«µí¹A»êðÔ·
            for(int i = 0; i < 5; i++)
                if(field[y][i]!=-1)
                    res+=seiseki[getValue(s,i)];
            return res;
        }
    }
    if(dp[y][x][s]!=INF)
        return dp[y][x][s];
    int maxCost=0;
    // »Ýn_ð½ñ·©
    for(int i = 0; i <= 3; i++){
        if(x==0){
            int ns=0;
            setValue(ns,5,getValue(s,4));
            setValue(ns,4,getValue(s,3));
            setValue(ns,3,getValue(s,2));
            setValue(ns,2,(getValue(s,1)+i)%4);
            setValue(ns,1,(max(0,field[y+1][x+1])+i)%4);
            setValue(ns,0,(max(0,field[y+1][x])+i)%4);
            // ¶ãÌêÌXRAðmè³¹é
            int res=0;
            if(field[y][x]!=-1)
                res+=seiseki[(getValue(s,x)+i)%4];
            // rec
            maxCost=max(maxCost,res+rec(x+1,y,ns));
        }
        else if(x==1){
            int ns=0;
            for(int j = 0; j < 6; j++){
                if(j==1||j==3)
                    setValue(ns,j,(getValue(s,j)+i)%4);
                else
                    setValue(ns,j,getValue(s,j));
            }
            setValue(ns,2,(max(0,field[y+1][x+1])+i)%4);
            // ¶ãÌêÌXRAðmè³¹é
            int res=0;
            if(field[y][x]!=-1)
                res+=seiseki[(getValue(s,2)+i)%4];
            maxCost=max(maxCost,res+rec(x+1,y,ns));
        }
        else if(x==2){
            int ns=0;
            for(int j = 0; j < 6; j++){
                if(j==2||j==4)
                    setValue(ns,j,(getValue(s,j)+i)%4);
                else
                    setValue(ns,j,getValue(s,j));
            }
            setValue(ns,3,(max(0,field[y+1][x+1])+i)%4);
            // ¶ãÌêÌXRAðmè³¹é
            int res=0;
            if(field[y][x]!=-1)
                res+=seiseki[(getValue(s,3)+i)%4];
            maxCost=max(maxCost,res+rec(x+1,y,ns));
        }
        else if(x==3){
            int ns=0;
            for(int j = 0; j < 6; j++){
                if(j==3||j==5)
                    setValue(ns,j,(getValue(s,j)+i)%4);
                else
                    setValue(ns,j,getValue(s,j));
            }
            setValue(ns,4,(max(0,field[y+1][x+1])+i)%4);
            // ¶ãÌêÌXRAðmè³¹é
            int res=0;
            if(field[y][x]!=-1)
                res+=seiseki[(getValue(s,4)+i)%4];
            // EãÌXRAàmè³¹é
            if(field[y][x+1]!=-1)
                res+=seiseki[(getValue(s,5)+i)%4];
            maxCost=max(maxCost,res+rec(x+1,y,ns));
        }
    }
    return dp[y][x][s]=maxCost;
}


int main(){
    seiseki[0]=0;
    seiseki[1]=60;
    seiseki[2]=70;
    seiseki[3]=80;
    cin>>n;
    for(int q=0;q<n;q++){
        for(int i = 0; i < 6; i++)
            for(int j = 0; j < 6; j++)
                for(int k = 0; k < (1<<12); k++)
                    dp[i][j][k]=INF;
        for(int i = 0; i < 5; i++){
            for(int j = 0; j < 5; j++){
                cin>>field[i][j];
                field[i][j]--;
            }
        }
        int s=0;
        for(int i = 0; i < 5; i++)
            setValue(s,i,max(0,field[0][i]));
        int res=rec(0,0,s);
        cout<<res<<endl;
    }
    return 0;
}