//8queen
#include<iostream>
using namespace std;
int M,N;
int a[8][8];
int arr[8];
int ans;
bool safe(int r,int c){
for(int i=0;i<r;i++){
if(arr[i]==c)return false;
if(i-arr[i]==r-c)return false;
if(arr[i]+i==r+c)return false;
}
return true;
}
void backtrack(int k)
{
if(k== 8){
int sum=0;
for(int i=0;i<8;i++){
sum += a[i][arr[i]];
}
if(sum>ans)
ans=sum;
return;
}
for(int i=0; i<8; i++){
if(safe(k,i)){
arr[k]=i;
backtrack(k+1);
}
}
}
int main()
{
//freopen("Text.txt","r",stdin);
int t;
cin >> t;
for(int tc= 1; tc <=t; tc ++)
{
int n;
cin>>n;
cout << "Case #" << tc<<endl;
for(int u=0;u<n;u++){
for(int i=0 ; i <8; i++)
{
for(int j=0 ; j <8; j++)
{
cin >> a[i][j];
}
}
ans =0;
backtrack(0);
cout << ans<< endl;
}
}
return 0;
}
// di chuyen bo
#include<iostream>
using namespace std;
int M,N;
int W[16];
int ans;
int sum;
void backtrack(int k)
{
if(sum > M) {
return;
}
if(k== N){
if(sum > ans ){ ans = sum;}
return ;
}
for(int i=0; i<2; i++){
if(i==0){
backtrack(k+1);
}
else {
sum+= W[k];
backtrack(k+1);
sum-= W[k];
}
}
}
int main()
{
//freopen("Text.txt","r",stdin);
int t;
cin >> t;
for(int tc= 1; tc <=t; tc ++)
{
cin >> M >> N;
for(int i=0 ; i <N; i++)
{
cin >> W[i];
}
ans =-1;
sum=0;
backtrack(0);
cout << "#" << tc << " " << ans<< endl;
}
return 0;
}
//chess
#include<iostream>
using namespace std;
int N;
char arr[4][4];
int ans;
bool safe(int r,int c){
if(arr[r][c]=='X')return false;
for(int i=c-1;i>=0;i--){
if(arr[r][i]=='C')return false;
else if(arr[r][i]=='X')break;
}
for(int i=r-1;i>=0;i--){
if(arr[i][c]=='C')return false;
else if(arr[i][c]=='X')break;
}
return true;
}
void reset(){
}
void backtrack(int k){
if(k== N*N){
int cnt=0;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(arr[i][j]=='C'){
cnt++;
}
}
}
if (cnt>ans)ans=cnt;
return;
}
if(safe(k/N,k%N)){
for(int i=0; i<2; i++){
if(i==0){
backtrack(k+1);
}
if(i==1){
arr[k/N][k%N]='C';
backtrack(k+1);
arr[k/N][k%N]='.';
}
}
}else backtrack(k+1);
}
int main()
{
//freopen("Text.txt","r",stdin);
int t;
cin >> t;
for(int tc= 1; tc <=t; tc ++)
{
cin>>N;
for(int i=0 ; i <N; i++)
{
for(int j=0 ; j <N; j++)
{
cin >> arr[i][j];
}
}
ans =0;
backtrack(0);
cout <<"Case #"<<tc<<endl<< ans<< endl;
}
return 0;
}