#include <stdio.h>
#include <vector>
#include <string>
#include <iostream>
#include <math.h>
using namespace std;
 
class Solution {
public:
    vector<vector<string> > ans;
    bool safe(vector<string>& board, int i, int j){
        if (board[i][j]=='Q')return false;
        int n = board.size();
        for(int a=0; a<i;  ++a)
            if ( board[a][j]=='Q')return false; 
 
        for(int k1=i-1, k2=j-1; k1>=0 and k2>=0; k1--, k2--)
            if (board[k1][k2]=='Q')return false;
 
        for(int k1=i-1, k2=j+1; k1>=0 and k2<n; k1--, k2++)
            if (board[k1][k2]=='Q')return false;
 
        return true;
    }
    bool solveNQueens(int n) {
        vector<string> board(n, string(n, '.'));
 
        int breakBound = 0;
        if ( (2*n)%3==0)breakBound = (2*n/3 + 1);
        else breakBound = ceil(2.0*n/3.0);
 
        return solve(board, breakBound,-1);       
    }
    bool solve(vector<string>& board,  int queens_left, int last_i){
        if (queens_left==0){
            cout << "FALSE CONJECTURE";
            ans.push_back(board);
            return true;
        }
        int n = board.size();
        for(int j=(last_i+1)%2; j<n; j+=2){
            if (safe(board, last_i+1, j)){
                board[last_i+1][j] = 'Q';
                bool s = solve(board, queens_left-1, last_i+1);
                if (s)return true;
                board[last_i+1][j] = '.';
            }
        }
        return false;
    }
};
 
int main(int argc, char** argv) {
    Solution S;
    cout << S.solveNQueens(25) << endl;
    for(auto& board : S.ans){
        for(int i=0; i<board.size(); ++i){
            for(int j=0; j<board[i].size(); ++j){
                cout << board[i][j] << " ";
            }
            cout << endl;
        }
    }
    cout << endl << endl;
}
 

I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxzdHJpbmc+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPG1hdGguaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmNsYXNzIFNvbHV0aW9uIHsKcHVibGljOgogICAgdmVjdG9yPHZlY3RvcjxzdHJpbmc+ID4gYW5zOwogICAgYm9vbCBzYWZlKHZlY3RvcjxzdHJpbmc+JiBib2FyZCwgaW50IGksIGludCBqKXsKICAgICAgICBpZiAoYm9hcmRbaV1bal09PSdRJylyZXR1cm4gZmFsc2U7CiAgICAgICAgaW50IG4gPSBib2FyZC5zaXplKCk7CiAgICAgICAgZm9yKGludCBhPTA7IGE8aTsgICsrYSkKICAgICAgICAgICAgaWYgKCBib2FyZFthXVtqXT09J1EnKXJldHVybiBmYWxzZTsgCiAgICAgICAgCiAgICAgICAgZm9yKGludCBrMT1pLTEsIGsyPWotMTsgazE+PTAgYW5kIGsyPj0wOyBrMS0tLCBrMi0tKQogICAgICAgICAgICBpZiAoYm9hcmRbazFdW2syXT09J1EnKXJldHVybiBmYWxzZTsKICAgICAgICAKICAgICAgICBmb3IoaW50IGsxPWktMSwgazI9aisxOyBrMT49MCBhbmQgazI8bjsgazEtLSwgazIrKykKICAgICAgICAgICAgaWYgKGJvYXJkW2sxXVtrMl09PSdRJylyZXR1cm4gZmFsc2U7CiAgICAgICAgCiAgICAgICAgcmV0dXJuIHRydWU7CiAgICB9CiAgICBib29sIHNvbHZlTlF1ZWVucyhpbnQgbikgewogICAgICAgIHZlY3RvcjxzdHJpbmc+IGJvYXJkKG4sIHN0cmluZyhuLCAnLicpKTsKCiAgICAgICAgaW50IGJyZWFrQm91bmQgPSAwOwogICAgICAgIGlmICggKDIqbiklMz09MClicmVha0JvdW5kID0gKDIqbi8zICsgMSk7CiAgICAgICAgZWxzZSBicmVha0JvdW5kID0gY2VpbCgyLjAqbi8zLjApOwogICAgICAgIAogICAgICAgIHJldHVybiBzb2x2ZShib2FyZCwgYnJlYWtCb3VuZCwtMSk7ICAgICAgIAogICAgfQogICAgYm9vbCBzb2x2ZSh2ZWN0b3I8c3RyaW5nPiYgYm9hcmQsICBpbnQgcXVlZW5zX2xlZnQsIGludCBsYXN0X2kpewogICAgICAgIGlmIChxdWVlbnNfbGVmdD09MCl7CiAgICAgICAgICAgIGNvdXQgPDwgIkZBTFNFIENPTkpFQ1RVUkUiOwogICAgICAgICAgICBhbnMucHVzaF9iYWNrKGJvYXJkKTsKICAgICAgICAgICAgcmV0dXJuIHRydWU7CiAgICAgICAgfQogICAgICAgIGludCBuID0gYm9hcmQuc2l6ZSgpOwogICAgICAgIGZvcihpbnQgaj0obGFzdF9pKzEpJTI7IGo8bjsgais9Mil7CiAgICAgICAgICAgIGlmIChzYWZlKGJvYXJkLCBsYXN0X2krMSwgaikpewogICAgICAgICAgICAgICAgYm9hcmRbbGFzdF9pKzFdW2pdID0gJ1EnOwogICAgICAgICAgICAgICAgYm9vbCBzID0gc29sdmUoYm9hcmQsIHF1ZWVuc19sZWZ0LTEsIGxhc3RfaSsxKTsKICAgICAgICAgICAgICAgIGlmIChzKXJldHVybiB0cnVlOwogICAgICAgICAgICAgICAgYm9hcmRbbGFzdF9pKzFdW2pdID0gJy4nOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIHJldHVybiBmYWxzZTsKICAgIH0KfTsKCmludCBtYWluKGludCBhcmdjLCBjaGFyKiogYXJndikgewogICAgU29sdXRpb24gUzsKICAgIGNvdXQgPDwgUy5zb2x2ZU5RdWVlbnMoMjUpIDw8IGVuZGw7CiAgICBmb3IoYXV0byYgYm9hcmQgOiBTLmFucyl7CiAgICAgICAgZm9yKGludCBpPTA7IGk8Ym9hcmQuc2l6ZSgpOyArK2kpewogICAgICAgICAgICBmb3IoaW50IGo9MDsgajxib2FyZFtpXS5zaXplKCk7ICsrail7CiAgICAgICAgICAgICAgICBjb3V0IDw8IGJvYXJkW2ldW2pdIDw8ICIgIjsKICAgICAgICAgICAgfQogICAgICAgICAgICBjb3V0IDw8IGVuZGw7CiAgICAgICAgfQogICAgfQogICAgY291dCA8PCBlbmRsIDw8IGVuZGw7Cn0K