#include <list>
#include <vector>
#include <fstream>

inline int abs(int x) {
	return x < 0 ? -x : x;
}

std::list < std::vector< int > > go(int &n) {
	
	static std::vector<int> rec;

	if(rec.size() == n)
		return std::list < std::vector<int> > (1, rec);
	else {
		
		std::list < std::vector<int> > r;
		for(int i = 0; i < n; i++) {

			bool valid = true;
			for(int j = 0; j < rec.size(); j++) {
				if(rec[j] == i || rec.size() - j == abs(i - rec[j]))
					valid = false;
			}

			if(valid) {
				rec.push_back(i);
				std::list < std::vector<int> > r2 = go(n);
				r.splice(r.end(), r2);
				rec.pop_back();
			}
		}

		return r;
	}
}

int main() {
	
	std::ifstream fin("damesah.in",std::ios::in);
	std::ofstream fout("damesah.out",std::ios::out);

	int n;
	fin>>n;

	std::list< std::vector<int> > r = go(n);
	
	if(!r.empty()) {
		
		for(int i = 0; i < r.begin()->size(); i++) {
			fout << r.begin()->operator[](i) + 1 << ' ';
		}
		fout << std::endl;
	}
	fout << r.size() << std::endl;
	
	return 0;
}