18821번 - 홀수와 짝수의 대결 서브태스크

문제

1 이상 n 이하의 자연수 중 짝수가 더 많을까, 홀수가 더 많을까?

입력

첫째 줄에는 테스트케이스의 개수 T(0 이상 1,000,000 이하)가 주어진다. 각각의 테스트케이스는 한 줄로 이루어져 있으며, 그 줄에 1 이상 10⁹ 이하의 자연수 n이 주어진다.

출력

각 테스트케이스마다 한 줄씩, 짝수가 홀수보다 (削除) 많으면 (削除ここまで) 적지 않으면 O, 아니면 E를 출력한다.

네, 참으로 올바르시겠어요...

제한

서브태스크 1 (123456789점)

n <= 1,000

서브태스크 2 (456789012점)

n <= 10,000,000

서브태스크 3 (1567237846점)

추가 제약 조건이 없다.

노트

문제가 너무 쉽기 때문에 그나마 구데기스럽게 만들기 위해 예제를 숨겼다.

• 예제는 채점하지 않는다.

일반적인 정의와 달리 이 문제에서는 홀수와 짝수를 다음과 같이 정의한다.

1 이상의 자연수 k는 소수의 곱으로 표현할 수 있고, 그 표현 방법은 소수의 순서를 바꾸는 경우를 제외하면 유일하다. 이때 사용된 소수의 개수가 2의 배수가 아니면 k는 짝수, 아니면 k는 홀수이다. (k = 1일 때는 소수 0개의 곱이고, 0은 2의 배수이다.) 같은 소수가 여러 번 사용되었을 경우, 사용될 때마다 하나씩 세어야 한다.