Factorial Factors

Interview

Time limit1sMemory limit512 MB

Summary

For each N up to 100,000, count the distinct prime factors of N! and the total number of prime factors with multiplicity.

Level: Medium4 of 10
Topics: Number theory, Math, Prefix sum, Implementation
Solved: No attempts yet

Problem

The factorial of a number N, written N!, is the product of all integers from 1 to N, inclusive. For example, 5! = 120.

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

This problem concerns the prime factorization of a factorial. You must determine the number of total and distinct prime factors. In the example above, there are 5 total prime factors (2, 2, 2, 3, 5) and 3 distinct prime factors (2, 3, 5).

Input

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

Output

For each test case, print a single line D T, where D is the number of distinct prime factors of N! and T is the total number of prime factors of N!.

Examples1

Example 1
Input
```
2
5
6
```
Expected output
```
3 5
3 7
```