#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <time.h>

#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <string.h>
#include <vector>
#include <stdio.h>
#include <algorithm>
using namespace std;

typedef unsigned long long llu;
typedef long long lld;

const int MAXN = 2e5 + 10;
const int INF = 1e9;
const int BASE = 10000;

int gcd(int a, int b)
{
	if (a == 0)return b;
	if (b == 0)return a;
	if (a%b == 0)return b;
	return gcd(b, a%b);
}

struct BigNum
{
	static int MOD_LEN;
	int len;
	int dig[256];
	BigNum()
	{
		Clear();
	}
	void Clear()
	{
		len = 1;
		memset(dig, 0, sizeof(dig));
	}

	void Mod()
	{
		while (len > MOD_LEN)
		{
			len--;
			dig[len] = 0;
		}
	}

	void SetNum(const char* s)
	{
		Clear();
		int slen = strlen(s);
		len = 0;
		for (int i = slen - 1; i >= 0;)
		{
			int d = 0;
			int t = 1;
			for (int j = 0; j < 4 && i >= 0; j++, i--)
			{
				d += t * (s[i] - '0');
				t *= 10;
			}

			dig[len] = d;
			len++;
		}
		RemoveLeadingZero();
		Mod();
	}

	void SetNum(int n)
	{
		Clear();
		if (n == 0)
		{
			return;
		}

		len = 0;
		while (n)
		{
			dig[len] = n % BASE;
			n /= BASE;
			len++;
		}

		Mod();
	}

	void Print()
	{
		printf("%d", dig[len - 1]);
		for (int i = len - 2; i >= 0; i--)
		{
			printf("%04d", dig[i]);
		}
	}

	int Compare(const BigNum& other) const
	{
		if(len<other.len)
		{
			return -1;
		}
		else if (len > other.len)
		{
			return 1;
		}
		else
		{
			for (int i = len - 1; i >= 0; i--)
			{
				if (dig[i] != other.dig[i])
				{
					return dig[i] - other.dig[i];
				}
			}
			return 0;
		}
	}

	void operator++()
	{
		dig[0]++;
		int i = 0;
		while (dig[i] >= BASE)
		{
			dig[i] -= BASE;
			dig[i + 1]++;
			i++;
		}
		if (dig[len])
		{
			len++;
		}

		Mod();
	}

	void operator*=(const BigNum& other)
	{
		lld dc[256] = { 0 };

		int lenc = len + other.len;
		if (lenc > MOD_LEN)
		{
			lenc = MOD_LEN;
		}

		for (int i = 0; i < len && i < MOD_LEN; i++)
		{
			for (int j = 0; j < other.len && i + j < MOD_LEN; j++)
			{
				dc[i + j] += dig[i] * other.dig[j];
			}
		}

		for (int i = 0; i < lenc; i++)
		{
			if (dc[i] >= BASE)
			{
				dc[i + 1] += dc[i] / BASE;
				dc[i] %= BASE;
			}

			dig[i] = dc[i];
		}

		len = lenc;
		RemoveLeadingZero();

		Mod();
	}

	void RemoveLeadingZero()
	{
		while (len > 1 && dig[len - 1] == 0)
		{
			len--;
		}
	}

	void operator+=(const BigNum& other)
	{
		len = max(len, other.len);
		for (int i = 0; i < len; i++)
		{
			dig[i] += other.dig[i];
			if (dig[i] >= BASE)
			{
				dig[i + 1]++;
				dig[i] -= BASE;
			}
		}

		if (dig[len])
		{
			len++;
		}

		Mod();
	}

	void operator/=(int d)
	{
		if (d == 1)
		{
			return;
		}
		for (int i = len - 1; i > 0; i--)
		{
			dig[i - 1] += (dig[i] % d)*BASE;
			dig[i] /= d;
		}

		if (dig[0] % d != 0)
		{
			while (1)
			{
				cout << "error" << endl;
			}
		}

		dig[0] /= d;

		RemoveLeadingZero();

		Mod();
	}

	BigNum operator-(const BigNum& other) const
	{
		BigNum c;
		c.len = len;
		for (int i = 0; i < len; i++)
		{
			c.dig[i] = dig[i] - other.dig[i];
		}

		for(int i=0;i<len;i++)
		{ 
			if (c.dig[i] < 0)
			{
				c.dig[i] += BASE;
				c.dig[i + 1]--;
			}
		}

		c.RemoveLeadingZero();
		c.Mod();
		return c;
	}

};

int BigNum::MOD_LEN = 1;

BigNum f[16][16];

void ReadBigNum(BigNum& N)
{
	char s[256];
	scanf("%s", s);
	N.SetNum(s);
}

BigNum Pow(BigNum n, int m)
{
	BigNum ret;
	ret.SetNum(1);
	while (m)
	{
		if (m & 1)
		{
			ret *= n;
		}

		n *= n;
		m >>= 1;
	}

	return ret;
}

BigNum Fun(const BigNum& x, const BigNum* a, int m)
{
	BigNum result = a[m];
	for (int i = m - 1; i >= 0; i--)
	{
		result *= x;
		result += a[i];
	}

	return result;
}

BigNum SolveSimple(const BigNum& L, int len, const BigNum* a, int m)
{	
	BigNum tempL = L;

	for (int i = 0; i <len; i++)
	{
		f[0][i] = Fun(tempL, a, m);
		++tempL;
	}

	BigNum ans;
	return ans;
}

int DigSqrSum(int x, int last)
{
	int ret = 0;
	while (last > 0)
	{
		last--;
		int d = x % 10;
		x /= 10;
		ret += d * d;
	}

	return ret;
}

int GetSqrSum(const BigNum& n, int last)
{
	int ans = 0;
	for (int i = 0; i < n.len && last>0; i++)
	{
		if (last >= 4)
		{
			ans += DigSqrSum(n.dig[i],4);
			last -= 4;
		}
		else
		{
			ans += DigSqrSum(n.dig[i], last);
			last = 0;
		}

	}

	return ans;
}

void SolveCombination(int m, const BigNum* a, const BigNum& L, int k, int last)
{
	if (k <= m + 3)
	{
		SolveSimple(L, k, a, m);
		for (int i = 0; i < k; i++)
		{
			int sqrSum = GetSqrSum(f[0][i], last);
			printf("%d\n", sqrSum);
		}
		return;
	}

	SolveSimple(L, m + 1, a, m);

	for (int i = 0; i < m + 1; i++)
	{
		int sqrSum = GetSqrSum(f[0][i], last);
		printf("%d\n", sqrSum);
	}

	BigNum c[16];

	for (int i = 1; i <= m; i++)
	{
		for (int j = i; j <= m; j++)
		{
			f[i][j] = f[i - 1][j] - f[i - 1][j - 1];
		}
	}

	for (int i = 0; i <= m; i++)
	{
		c[i] = f[i][m];
	}

	for (int i = m + 1; i < k; i++)
	{
		for (int j = m-1; j >= 0; j--)
		{
			c[j] += c[j + 1];
		}

		int ans = GetSqrSum(c[0], last);
		printf("%d\n", ans);
	}
}

lld Brt(const BigNum& N, int m)
{
	lld ans = 0;
	for (int i = 1; i <= N.dig[0]; i++)
	{
		lld x = 1;
		for (int j = 0; j < m; j++)
		{
			x *= i;
		}

		ans += x;
	}

	return ans;
}

int main(int argc, char *argv[]) {
	
	int T;
	cin >> T;
	while (T--)
	{
		int m;
		cin >> m;
		BigNum L;
		ReadBigNum(L);
		int k;
		int last;
		cin >> k >> last;

		BigNum::MOD_LEN = (last + 3) / 4;

		BigNum a[16];
		for (int i = m; i >= 0; i--)
		{
			ReadBigNum(a[i]);
		}
		
		SolveCombination(m, a, L, k, last);
	}
	return 0;
}

/*

*/