팩토리얼 제곱의 배수

여러 개의 N에 대해 (N!)^2이 K!을 나누는 가장 작은 K를 구한다. 답은 항상 N과 2N 사이에 있고 르장드르 지수 계산이 필요하다.

어려움8정수론수학이분 탐색구현아직 제출이 없습니다시간 제한3초메모리 제한512 MB

문제 설명

예제1

양의 정수 $N$ 이 주어진다. $K!$ 이 $(N!)^2$ 의 배수가 되는 가장 작은 양의 정수 $K$ 를 구하라.

$a = b \times k$ 를 만족하는 정수 $k$ 가 존재하면 $a$ 는 $b$ 의 배수이다. 또한 양의 정수 $M$ 에 대해 $M!$ 은 $M$ 이하인 모든 양의 정수의 곱이다.

첫째 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 이어지는 $T$ 개의 줄에는 각 테스트 케이스의 정수 $N$ 이 한 줄에 하나씩 주어진다.

제약 조건

각 테스트 케이스마다 답을 한 줄에 하나씩 출력한다.