Our goal is to solve each test in $O(1)$ time.

First, let's check whether $x=0$. We can do this by exchanging chips of type B to A as many times as possible, then checking whether we have at least $f_A$ chips of type A.

Python snippet:

init = B // cB * cA + A
if init >= fA:
    return 0

Otherwise, $x>0$. For convenience, let's compute $y = x-1$ instead, then add one to $y$ at the end to get the final answer. Here, $y$ equals the maximum possible value of $n_A+n_B$ over all valid ordered pairs of non-negative integers $(n_A, n_B)$, where $(n_A,n_B)$ is valid if we cannot form $f_A$ chips of type A after receiving $n_A$ chips of type A and $n_B$ chips of type B. Mathematically, the following inequality must hold:

At least one valid pair exists since $(0,0)$ is valid.

Subtask $x\le 10$: If we're given an upper bound $X$ such that $x\le X$, then it suffices to check validity only for pairs of non-negative integers $(n_A, n_B)$ such that $n_A+n_B<X$. This takes $O(X^2)$ time, which is fast enough for $X=10$.

Full Solution: First observe that the valid pair with maximum sum must satisfy $B+n_B\equiv c_B-1 \pmod {c_B}$ (if not, then there would be a contradiction because increasing $n_B$ by one would give a valid pair with greater sum). Therefore, if we define $n_{B,0}=c_B-1-(B\pmod {c_B})$, then $n_B=n_{B,0}+ic_B$ for some non-negative integer $i$ we need to determine.

Define $n_{A,0}$ such that $(n_{A,0}, n_{B,0})$ is the valid pair with maximum sum when the second element of the pair is fixed to be $n_{B,0}$. Then $n_A=n_{A,0}-c_Ai$. To choose $i$ so that $n_A+n_B$ is maximized, we should either

• minimize $i$ if $c_A\ge c_B$ (that is, set $i=0$)
• otherwise, set $i$ to be the maximum possible value such that $n_{A,0}-c_Ai\ge 0$ (that is, set $i=\lfloor n_{A,0}/c_A\rfloor$).

Python full solution:

def solve(A, B, cA, cB, fA):
    init = B // cB * cA + A
    if init >= fA:
        return 0
    nA0 = fA - 1 - init
    y = cB - 1 - B % cB  # nB0
    if cA >= cB:
        y += nA0
    else:
        y += nA0 // cA * cB + nA0 % cA
    return y + 1

def main():
    T = int(input())
    for _ in range(T):
        A, B, cA, cB, fA = map(int, input().split())
        print(solve(A, B, cA, cB, fA))

if __name__ == "__main__":
    main()