P6222 "P6156 Easy Problem" Enhanced Version.

[Original problem link](https://www.luogu.com.cn/problem/P6156). Based on the original problem, this version adds multiple testcases, changes the modulus, and increases the Constraints to completely block non-linear preprocessing. It may be somewhat tight on constant factors.

There are $T$ queries. At the beginning, you are given a constant $K$. In each query, you are given $n$ separately. Please compute: $$\sum_{i=1}^{n}\sum_{j=1}^{n} (i+j)^K \gcd(i,j) \mu^2(\gcd(i,j)) \pmod {2^{32}}$$

The first line contains three positive integers $T, N, K$, representing the number of queries, the maximum value of $N$ among the queries, and the given constant. In the next $T$ lines, each line contains one positive integer, representing the value of $n$ for that query.

Output $T$ lines. Each line contains one non-negative integer, representing the result of evaluating the expression in the statement for the given $n$.

There are $5$ groups of testdata. Group $i$ satisfies: $N=10^{i+2}$. For all testdata, it holds that: $T = 10^4$, $1 \leq K < 2^{31}$. Translated by ChatGPT 5