Марин хочет, чтобы вы посчитали количество красивых перестановок. Красивой перестановкой длины $$$n$$$ называется перестановка, обладающая следующим свойством: $$$$$$ \gcd (1 \cdot p_1, \, 2 \cdot p_2, \, \dots, \, n \cdot p_n) > 1, $$$$$$ где $$$\gcd$$$ — это наибольший общий делитель.

Перестановка — это массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. К примеру, $$$[2,3,1,5,4]$$$ является перестановкой, а $$$[1,2,2]$$$ — не является ($$$2$$$ встречается в массиве дважды), как и массив $$$[1,3, 4]$$$ ($$$n=3$$$, но в массиве присутствует $$$4$$$).