Description

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}}$$

Input Format

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 Format

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

4 1919 5
1
14
51
4

32
1012884514
62017882
105160

Hint

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