Subtask 1: $n\le 20$

Vì giới hạn $n$ nhỏ, ta có thể quay lui kiểm tra tất cả trường hợp. Mỗi trường hợp ta kiểm tra xem nó có là số chính phương hay không.

Độ phức tạp: $O(2^n)$

Subtask 2: $n\le 10^5$

Đầu tiên ta phân tích $n!$ thành thừa số nguyên tố. Gọi kết quả là $ans$, với mỗi tsnt $p$ có $k$ lần xuất hiện tsnt $p$ trong biểu diễn nguyên tố của $n!$, ta nhân $ans$ lên $p^{k-k\ mod\ 2}$

Độ phức tạp: $O(n\times log(n)^2)$