오비탈이 싫어

양의 정수 $x$가 어떤 양의 정수 $k$에 대해 $x=2k^2$를 만족하면, $x$를 오비수라고 하자.

양의 정수로 이루어진 길이 $N$의 수열 $A_1,A_2,\cdots,A_N$이 주어진다. 수열이 다음 조건 중 하나라도 만족하면 불안정한 수열이라고 한다.

• 수열의 어떤 원소가 오비수이다.
• 수열에서 서로 다른 두 위치의 원소를 골랐을 때, 두 원소의 곱이 오비수가 되는 경우가 존재한다.

주어진 수열에서 원소를 몇 개 지워 불안정한 수열이 아니게 만들고자 한다. 지워야 하는 원소 개수의 최솟값을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$N$ $A_1\ A_2\ \cdots\ A_N$

첫째 줄에 지워야 하는 원소 개수의 최솟값을 출력한다.

• $1 \leq N \leq 5\ 000$.
• $1 \leq A_i \leq 10^9$ ($1 \leq i \leq N$).