시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 1 1 1 100.000%

문제

The factorial of a number N, written N!, is the product of all integers between 1 and N, inclusively. For example, 5! = 120.

Every integer greater than 1 can be written as the product of 1 or more prime numbers, some of which may repeat. For example, 120 = 2 * 2 * 2 * 3 * 5.

For this problem, we are interested in the prime factorization of the factorial of a number. You will need to determine the number of total and distinct prime factors. For the example above, there are 5 total prime factors (2, 2, 2, 3, 5) and 3 distinct prime factors (2, 3, 5).

입력

The first line of input will contain the number of test cases, C (1 ≤ C ≤ 50). Each test case will consist of a single line containing an integer N (2 ≤ N ≤ 100,000).

출력

Each test case will result in a single line of output D T where D is the number of distinct prime factors of N! and T is the total number of prime factors of N!.

예제 입력 1

2
5
6

예제 출력 1

3 5
3 7