#![allow(non_snake_case)]
use text_io::read;
use rand::rngs::ThreadRng;
use std::fmt::{Display, Formatter, Result};
use std::time::Instant;

pub const MAXN: usize = 10010;

#[derive(Debug)]
pub struct Puzzle {
    in_col:  [usize; MAXN],       // Позиция в колона
    per_row: [i32; MAXN],         // Бройка на ред
    per_d1:  [i32; 2 * MAXN - 1], // Бройка на главен диагонал
    per_d2:  [i32; 2 * MAXN - 1], // Бройка на втори диагонал

    N: usize,
    rng: ThreadRng,
}

impl PartialEq for Puzzle {
    fn eq(&self, other: &Puzzle) -> bool {
        (self.in_col == other.in_col) &&
        (self.per_row == other.per_row) &&
        (self.per_d1 == other.per_d1) &&
        (self.per_d2 == other.per_d2) &&
        (self.N == other.N)
    }
}

mod helper;
mod cell;
mod alg;

impl Display for Puzzle {
    fn fmt(&self, f: &mut Formatter) -> Result {
        for row in 0..self.N {
            for col in 0..self.N {
                if self.in_col[col] == row {
                    write!(f, "*")?;
                }
                else {
                    write!(f, "_")?;
                }
                if col < self.N - 1 {
                    write!(f, " ")?;
                }
            }
            writeln!(f, "")?;
        }
        Ok(())
    }
}

fn main() {
    let N: usize = read!();
    if N == 2 || N == 3 {
        println!("-1");
        return;
    }
    let mut task = Puzzle::new(N);

    let start = Instant::now();
    task.solve();
    let elapsed = start.elapsed();

    if N > 100 {
        println!("{:.2}", elapsed.as_secs_f64());
    }
    else {
        println!("{}", task);
    }
}