欧拉

题号：NC18949
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小w是欧拉的粉丝

众所周知

$\phi(n) = \sum_{d\mid n}d\mu(\frac{n}{d})$
$\phi$ 为欧拉函数， $\mu$ 为莫比乌斯函数
现在小w想求这个东西

$F(n) = \sum_{d\mid n}d^k\mu(\frac{n}{d})$
有m次询问，每次询问F(n)对998244353取mod

第一行两个数m和k
第二行到第m+1行，每行一个n

共m行，表示对于每次询问的F(n)

示例1

复制

1 3
8

复制

n ≤ 5000000
m ≤ 500000
1 ≤ k ≤ 100