package main

func countArrangement(n int) (res int) {
	valid := make([][]bool, n+1, n+1)
	for i := 1; i < n+1; i++ {
		valid[i] = make([]bool, n+1, n+1)
		for j := 1; j < n+1; j++ {
			if i%j == 0 || j%i == 0 {
				valid[i][j] = true
			}
		}
	}
	var backtrace func(idx int)
	used := make([]int, n+1, n+1)
	backtrace = func(idx int) {
		if idx > n {
			res++
			return
		}
		for i := 1; i <= n; i++ {
			if used[i] == 0 && (valid[idx][i] || valid[i][idx]) {
				used[i] = 1
				backtrace(idx + 1)
				used[i] = 0
			}
		}
	}
	backtrace(1)
	return res
}

func main() {

}