#include <bitset>
#include <vector>
using namespace std;

typedef long long ll;
const int MAX = (1 << 9) * (1 << 10);
const char FIN[] = "reg.in";
const char FOU[] = "reg.out";

int N, K, C;
int ies;

int A, B, MoD;

vector <int> numb;
bitset <MAX> if_is;

int main()
{
    int T, i, j, st, dr;

    freopen(FIN, "r", stdin);
    freopen(FOU, "w", stdout);


    for (scanf("%d", &T); T; --T)
    {

        scanf("%d %d %d %d %d", &A, &B, &C, &N, &K);

        numb.resize(C + 1);

        A %= C, B %= C;

        if ( A )
            for (MoD = 1; ((ll) MoD * A) % C != 1 ; MoD++);
        else
            MoD = -1;


        numb.clear () ;
        if_is.reset () ;

        ies = 0;

        for (st = i = 1; i <= N; ++i)
        {
            numb[ st ]++;
            st = (int) ( ((ll) A * st + (ll) B * (i + 1)) % C );
        }

        dr = st;

        for (i = st = 1, j = N + 1; i < j; ++i)
        {
            numb[ st ]--;

            if ( !if_is[ st ] )
                if (ies < K) ies++;
                else
                    for ( bool stop = 1 ; stop ; --j, --numb[ dr ] == 0 && if_is[ dr ] ? if_is[ dr ] = 0, stop = 0 : 0 )
                        if (MoD > 0)
                        {
                            dr = (dr + C - ((ll) B * j) % C) % C;
                            dr = ((ll) MoD * dr) % C;
                        }
                        else
                            dr = ((ll) B * (j - 1)) % C;

            if (numb[ st ] == 0)
                ies--;
            else
                if_is[ st ] = 1;

            st = (int) ( ((ll) A * st + (ll) B * (i + 1)) % C );
        }
        printf("%d\n", j - 1);
    }

    return 0;
}