#include <iostream>#include <cstdio>#include <cstring>#include <cmath>using namespace std;typedef long long ll;const int maxn = 1e6+5;const ll mod = 998244353;int sum[maxn];ll dp[maxn];ll cal(ll x, int n){ ll s = 1; while(n > 0) { if(n & 1) s = (s*x) % mod; x = (x*x)%mod; n >>= 1; } return s;}int main(){ int T; scanf("%d", &T); while(T--) { int n, k; scanf("%d %d", &n, &k); memset(sum, 0, sizeof(sum)); memset(dp, 0, sizeof(dp)); int MAX = 0; for(int i = 0; i < n; ++i) { int a; scanf("%d", &a); MAX = max(MAX, a); sum[a]++; } ll ans = 0; for(int i = MAX; i >= 1; --i) { int cnt = 0; for(int j = i; j <= MAX; j+=i) { cnt += sum[j]; dp[i] = (dp[i] - dp[j] + mod) % mod; } dp[i] = ((dp[i]+cal(2, cnt)-1)%mod + mod) % mod; ans = (ans + dp[i]*cal(i, k)) % mod; } printf("%lldn", ans); } return 0;}
