Subtask 1

Since ~N \le 4~, we can simply hard-code each test case.

~N = 1~:

Since ~1~ is the only permutation for ~N = 1~, the valid solution would just be ~1~.

~N = 2~:

The only permutations for ~N = 2~ would be ~1, 2~ and ~2, 1~. Since the sum of ~2~ and ~1~ is ~3~, which is prime, there is no valid solution.

~N = 3~:

Since the adjacent sum of ~1~ and ~2~ is ~3~, which is prime, we must keep the ~1~ and ~2~ apart. To keep ~1~ and ~2~ away from each other, we must put ~3~ in the middle, however this will not work as ~3~ will always be adjacent to ~2~, with a prime sum of ~5~. Therefore there is no valid solution.

~N = 4~:

In any permutation for ~N = 4~, a pair of adjacent even-odd numbers will always exist.

Since when ~N \le 4~, any even-odd pair will have a prime sum ~(3, 5, 7)~, there is no valid solution for ~N = 4~.

Time Complexity: ~\mathcal{O}(N)~

Subtask 2

We can simply brute-force each permutation of ~1, 2, \dots, N~ and determine whether or not a valid solution exists.

Time Complexity: ~\mathcal{O}(N!)~

Subtask 3

This subtask was left for inefficiencies in the implementation of the full solution or other solutions.

Full Solution

To guarantee that every adjacent sum in the permutation is non-prime, we can make all of them but the middle one even. To do this, we rearrange the numbers such that all even numbers are on one half of the permutation, and all odd numbers are on the other. This works since the sum of two even numbers or two odd numbers will always be even.

For the even-odd pair, we place ~5~ and ~4~ next to each other which results in the adjacent sum of ~9~, which is the first odd composite integer.

This approach works for ~N \ge 5~.

We can reuse subtask 1 solutions for ~N \le 4~.

Time Complexity: ~\mathcal{O}(N)~