class Program
        {
            static void Main(string[] args)
            {
                MainQueen();
            }
            static int count = 0;
            public static void MainQueen()
            {
                int n = Int32.Parse(Console.ReadLine());
                List<int> queen = new List<int>(n);
                for (int i = 1; i <= n; i++)
                {
                    queen.Add(0);
                }
                PutQueen(n, queen, 0);
                Console.WriteLine(count);
                Console.ReadKey();
            }

            private static void PutQueen(int n, List<int> queen, int row)
            {
                for (queen[row] = 1; queen[row] <= n; queen[row]++)
                {
                    if (CheckQueens(queen, row))
                    {
                        row++;
                        if (row < n)
                        {
                            PutQueen(n, queen, row);
                        }
                        else
                        {
                            count++;
                            for (int i = 0; i < n; i++)
                            {
                                Console.Write(queen[i].ToString() + " ");
                            }
                            Console.WriteLine();
                        }
                        row--;
                    }
                }
            }

            private static bool CheckQueens(List<int> queen, int row)
            {
                for (int i = 0; i < row; i++)
                {
                    if (Math.Abs(queen[i] - queen[row]) == Math.Abs(i - row) || queen[i] == queen[row])
                    {
                        return false;
                    }
                }
                return true;
            }
        }