bool check(int board[100][100], int row, int column, int n) {
    for (int i = 0; i < column; i++) {
        if (board[row][i] == 1) {
            return false;
        }
    }
    /*for (int i = n - 1; i > row; i++) {
        if ((board[i][column]) == 1) {
            return false;
        }
    }*/
    for (int i = 1; i <= n; i++) {
        if (column - i < 0) {
            break;
        }
        if (board[row - i][column - i] == 1) {
            return false;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (column - i < 0) {
            break;
        }
        if (board[row + i][column - i] == 1) {
            return false;
        }
    }
    return true;
}

void put(int board[100][100], int column, int n) {
    if (column == n) {
        counter++;
        cout << "number of solutions: " << counter << endl;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cout << board[i][j] << " ";
            }
            cout << endl;
        }
        cout << endl << endl;
    }
    for (int row = 0; row < n; row++) {
        board[row][column] = 1;
        if (check(board, row, column, n)) {
            put(board, column + 1, n);
        }
        board[row][column] = 0;
    }
}

int task16() { //Ферзи
    int n;
    cin >> n;
    int board[100][100];
    put(board, 0, n);
    return 0;
}