Description

$T$ 组询问。一开始给定一个常数 $K$。每次询问单独给定 $n$。请你求出：

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

Input Format

第一行三个正整数 $T,N,K$，分别表示询问组数、询问的 $N$ 的最大值、以及给定的常量。

接下来 $T$ 行，每行一个正整数表示这组询问的 $n$ 是多少。

Output Format

$T$ 行，每行一个非负整数，表示询问当前给定的 $n$，题面的式子计算出的结果是多少。

4 1919 5
1
14
51
4

32
1012884514
62017882
105160

Hint

一共有 $5$ 组测试点。第 $i$ 组测试点满足：$N=10^{i+2}$。

对于所有测试点，满足：$T = 10^4$，$1 \leq K < 2^{31}$。