G. Taking Breaks
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

After a long day of being orz, CodeTiger starts doing his homework. To be more effective, he has decided to plan out some breaks.

In CodeTiger's world, the day is $$$m$$$ seconds long, so clocks display integers between $$$0$$$ and $$$m-1$$$ inclusive. Specifically, $$$s$$$ seconds after CodeTiger starts working, the clock will display the integer $$$s \bmod m$$$.

CodeTiger decides that he will look at the clock at some points in time, and will take a break whenever he sees an integer on the clock less than or equal to a chosen integer $$$x$$$ (he is very genius, so his breaks last for a negligible amount of time).

Obviously, CodeTiger cannot always look at the clock, so he came up with some rules on when to look at the clock. The first time he looks at the clock is after $$$b$$$ seconds.

After that, suppose CodeTiger has looked at the clock $$$i$$$ times before, and the last time he looked was after $$$z$$$ seconds. Then he will next look at the clock after $$$(m-1)z+a(i\bmod c)^2$$$ seconds, where $$$a$$$ and $$$c$$$ are given constants.

CodeTiger will stop doing his homework after looking at the clock for the $$$n$$$-th time. How many breaks will CodeTiger take, if the clock initially displays $$$0$$$?

Input

Input consists of multiple tests. The first line contains $$$t$$$, the number of tests ($$$1 \le t \le 100$$$).

The next $$$t$$$ lines each contain $$$n$$$, $$$m$$$, $$$a$$$, $$$b$$$, $$$x$$$, and $$$c$$$ ($$$2 \le n,m,a,b \le 10^9$$$, $$$0 \le x \lt m$$$, $$$1 \le c \le 10^3$$$).

Output

For each testcase, print the number of breaks that CodeTiger takes.

Example
Input
4
4 9 2 3 4 5
69420 1000000000 6969 69420 999999999 420
142 48 474 706 40 921
210 873 131 32 592 572
Output
3
69420
124
142
Note

In the first test,

  • CodeTiger first looks at the clock at time $$$b=3$$$. At this point, the clock displays the time $$$3$$$. $$$3 \le x=4$$$, so he will take a break.
  • CodeTiger next looks at the clock at time $$$(m-1)\cdot 3 + a(1 \bmod c)^2 = 8\cdot 3 + 2\cdot 1 = 26$$$. At this time, the clock displays the time as $$$8$$$, so he does not take a break ($$$8 \gt x = 4$$$).
  • Codetiger next looks at the clock at time $$$(m-1)\cdot 26 + a(2 \bmod c)^2 = 8\cdot 26 + 2\cdot 4 = 216$$$. Here, the clock will display the time as $$$0$$$. $$$0 \le x = 4$$$, so CodeTiger takes a break.
  • Finally, CodeTiger looks at the clock at time $$$(m-1)\cdot 216 + a(3\bmod c)^2 = 8\cdot 216 + 2\cdot 9 = 1746$$$. At this time, the clock will display the time $$$0$$$, so he takes a break ($$$0 \le x = 4$$$).

In total, CodeTiger takes $$$3$$$ breaks.

In the second test, $$$x=m-1$$$, meaning that CodeTiger will take a break every time he looks at the clock. Therefore, we should output $$$n=69420$$$.

In the third test, note that it might be possible for $$$b \ge m$$$.