// 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 0
#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

int pr[3][10005];
int x[10005];
int N, K, B;

int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; }

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()+1, K = in(), B = in();
		memset(pr, 0, sizeof(pr));
		_x = x[0] = seed;
		for (i = 1; i < N; i++) {
			_x = 1 + ((_x + 12345) * _x) % M;
			x[i] = (int)_x;
		}
		for (i = 0; i < N; i++) {
			_x = x[i];
			for (j = bw[B]-1; j >= 0; j--) {
				a = bt[B][j];
				while (_x % a == 0) pr[j][i]++, _x /= a;
				if (_x == 1) break;
			}
		}
		ans = INF;
		for (j = bw[B]-1; j >= 0; j--) {
			qsort(pr[j], N, sizeof(int), cmp);
			a = 0;
			for (i = 0; i < K; i++) a += pr[j][i];
			a /= bp[B][j];
			if (a < ans) ans = a;
		}
		out(ans);
	}
	return 0;
}