题目背景

原题链接

此题在原题基础上，加上了多测，更改了模数，同时为了彻底卡掉非线性预处理，开大了数据范围。

可能有点卡常。

题目描述

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

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

输入输出格式

输入格式

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

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

输出格式

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

输入输出样例

输入样例 #1

4 1919 5
1
14
51
4

输出样例 #1

32
1012884514
62017882
105160

说明/提示

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

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