// yukicoder: No.28 末尾最適化
// 2019.4.9 bal4u
//
// 整数をB進数にしたときの、末尾のゼロの個数
// 
// 末尾のゼロの個数は
// Bが素数なら、その次数。例 8 = 2^3 = (1000)_2
// 
// Bが合成数なら、Bの素因数次数の最小値。
// 例 5000 = 5*10^3 = 5 * (2*5)^3 = 2^3 * 5^4。 
// 3と4の最小値は3。なので5000は末尾に0が3つ。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//// 高速入力
#if 1
#define gc() getchar_unlocked()
#define pc(c) putchar_unlocked(c)
#else
#define gc() getchar()
#define pc(c) putchar(c)
#endif
int in()    // 非負整数
{
	int n = 0, c = gc();
	//	while (isspace(c)) c = gc();
	do n = 10 * n + (c & 0xf), c = gc(); while (c >= '0');
	return n;
}

void out(int n)  // 非負整数の表示（出力）
{
	int i;
	char b[20];

	if (!n) pc('0');
	else {
		//		if (n < 0) pc('-'), n = -n;
		i = 0; while (n) b[i++] = n % 10 + '0', n /= 10;
		while (i--) pc(b[i]);
	}
	pc('\n');
}

//// 素因数分解モジュール
// 2~36の素因数分解
int bw[37], bt[37][3], bp[37][3]; // 2~36までの素因数とその次数

int ptbl[] = { 3,5,7,11,13,17,19,23,29,31,0 };  // 36までの素数表
void prime_factor(int n, int id)
{
	int d, sz;
	int *pp;

	sz = 0;
	if ((n & 1) == 0) {
		bt[id][sz] = 2;
		do n >>= 1, bp[id][sz]++;
		while ((n & 1) == 0);
		sz++;
	}
	for (pp = ptbl; n > 1 && *pp > 0; pp++) {
		if (n % *pp) continue;
		d = *pp;
		bt[id][sz] = d;
		do n /= d, bp[id][sz]++;
		while (n % d == 0);
		sz++;
	}
	if (n > 1) bt[id][sz] = n, bp[id][sz++] = 1;
	bw[id] = sz;
}

#define INF 0x7fffffff
#define M 100000009

typedef struct { int p[3]; } T;
T pr[10005];
int N, K, B;

void getPow(long long x, int *a)
{
	int i, b;

	for (i = bw[B] - 1; i >= 0; i--) {
		b = bt[B][i];
		while (x % b == 0) a[i]++, x /= b;
		if (x == 1) break;
	}
}

int cmp0(const void *a, const void *b) { return ((T *)a)->p[0] - ((T *)b)->p[0]; }
int cmp1(const void *a, const void *b) { return ((T *)a)->p[1] - ((T *)b)->p[1]; }
int cmp2(const void *a, const void *b) { return ((T *)a)->p[2] - ((T *)b)->p[2]; }

int main()
{
	int i, j, seed, Q, a, ans;
	long long x;

	for (i = 2; i <= 36; i++) prime_factor(i, i);
#if 0
	for (i = 2; i <= 36; i++) {
		int j;
		printf("%d w=%d:", i, bw[i]);
		for (j = 0; j < bw[i]; j++) printf(" (%d,%d)", bt[i][j], bp[i][j]);
		printf("\n");
	}
#endif

	Q = in();
	while (Q--) {
		seed = in(), N = in(), K = in(), B = in();
		memset(pr, 0, sizeof(pr));
		getPow(x = seed, pr[0].p);
		for (i = 1; i <= N; i++) {
			x = 1 + ((x + 12345) * x) % M;
			getPow(x, pr[i].p);
		}
		ans = INF;
		for (i = bw[B]-1; i >= 0; i--) {
			if (i == 2) qsort(pr, N+1, sizeof(T), cmp2);
			else if (i == 1) qsort(pr, N + 1, sizeof(T), cmp1);
			else qsort(pr, N + 1, sizeof(T), cmp0);
			a = 0;
			for (j = 0; j < K; j++) a += pr[j].p[i];
			a /= bp[B][i];
			if (a < ans) ans = a;
		}
		out(ans);
	}
	return 0;
}