Mock Euclid 2025 - Problem 7 Part B

Bessie the farmer is lining up her 20 sheep for their daily rations of food. There are a couple of conditions that the line must follow:

1. Odd numbered sheep cannot be adjacent to other odd numbered sheep.
2. Even numbered sheep cannot be adjacent to other even numbered sheep.
3. For two sheep numbered a and b, if a = b^n for an integer n > 1, then a must be to the right of b. For example, 9 must be to the right of 3 because 9=3^2.

If the number of ways the sheep can be arranged in a line can be expressed as \frac{(10!)^2}{n}, where n is a positive integer, find n.