Four functions problem This is not from online contest
Hi guys, a friend of mine recently give me this problem that I couldn't figure out an effective way to solve it.

Four functions
You are given four functions
$$
\begin{align}
A(x)&amp;=\text{Number of }i\text{ where }1\leq i\leq x\text{ and }\gcd(i,x)=1\\
B(x)&amp;=\sum_{d|x}A(d)\\
C(x)&amp;=\text{Sum of exponents of each prime in the prime factorization of }B(x)\\
D(x)&amp;=\sum_{i=1}^{x}C(x)
\end{align}
$$
Input:

First line: $T$ [number of test cases]
Each test case consists of an integer $N$

Output format
For each test case, print a single integer denoting the value of $D(N)$ in a new line.
Input constraints
$$\begin{align}1\leq T\leq 10^6\\1\leq N\leq 10^6\end{align}$$

Here's my observation:

About the constraints, there are 10^6 test cases, each test case can be as large as 10^6, I estimate we need an algorithm that is at least O(nlogn). Otherwise we will have TLE.

I guess this problem is a math one. We somehow need to come up with an efficient formula to resolve all 4 functions.

I know for sure if we solve this problem naively, we cannot pass all test cases. Even if we use the best method to compute gcd and prime factor.

I've thought about this one for two days I can't find an acceptable solution for this problem. You can assume that this problem have time limit of 5 seconds.


Since this is a math problem, some talented and gifted genius out there might be interested. :D
Please help to come up with a formula to solve this, or provide an understandable solution. Thank you very much.
Let me put together the two comments.
The function $A$ is Euler's totient function, which is often called $\phi$.
The function $B(x)=\sum_{d|n}\phi(d)$ is known to be equal to $B(x)=x$.
Now, observe that $D(x)=\sum_{i=1}^{x}C(B(i))=\sum_{i=1}^{x}C(i)=C(x!)$, where the last equation is because $C$ satisfies $C(a)+C(b)=C(ab)$.
Now, if $p_1&lt;p_2&lt;\ldots&lt;p_k$ are the primes less than or equal to $x$ and $x!=p_1^{a_1}p_2^{a_2}\dotsm p_k^{a_k}$, then $$C(x!)=a_1+a_2+...+a_k$$
We can use Legendre's formula to compute each $a_i$. Note that the formula doesn't need to compute $x!$, but it computes $$a_i=\left\lfloor\frac{x}{p_i}\right\rfloor+\left\lfloor\frac{x}{p_i^2}\right\rfloor+\left\lfloor\frac{x}{p_i^3}\right\rfloor+\ldots$$
where there are actually finitely many summands.
So, an algorithm to compute $D(x)$ can be:

Compute the primes $p_1,p_2,\ldots,p_k$ up to $x$. This can be done using some sieve, like Erathostenes' or Atkin's
Then for each prime evaluate Legendre's formula above, which takes about $\log_{p_i}(x)$ divisions.