Summation with GCD, Squarefree Filter and Exponentiation

You are given a constant K and T queries. For each query, an integer n is provided. Your task is to compute the following sum modulo 2^32:

$$ \sum_{i=1}^{n} \sum_{j=1}^{n} (i+j)^K \, \gcd(i,j) \; \mu^2(\gcd(i,j)) \pmod{2^{32}} $$

Here, the Möbius function \( \mu(\cdot) \) is used, and \( \mu^2(\cdot) \) ensures that only squarefree numbers (i.e. numbers not divisible by any square greater than 1) contribute (value is 1 if squarefree, and 0 otherwise).

inputFormat

The input begins with a line containing two integers T and K, where T is the number of queries and K is the fixed exponent.

Each of the following T lines contains one integer n for the corresponding query.

outputFormat

For each query, output one integer — the computed sum modulo 2^32, each on a separate line.

sample

1 2
3

336