Background

The problem is not very easy.

Description

简单而又和谐！两列简谐波的叠加是一个很有意思的问题。

你将会被给定两列简谐波：如果只有第一列简谐波，那么在$t$时刻这列简谐波的波形为$y=a\sin\frac{\pi px}{q}$；如果只有第二列简谐波，那么在$t$时刻这列简谐波的波形为$y=b\cos\frac{\pi px}{q}$。

现在你看到的是将这两列简谐波在$t$时刻叠加（可以理解为代数和）的照片，即波形$y=a\sin\frac{\pi px}{q}+b\cos\frac{\pi px}{q}$。

（接下来有$n,l,r∈\mathbb{N}_0$） 我们将提供$n$个观察点（即$n$个$x$的取值），这$n$个观察点依次为$[l,r]$之间的正整数（$n=r-l+1$）。 你需要找到一个观察点$x\in\{l,\dots,r\}$，使得这个点的位移大小（即$|y|$）最大，当多个$x$满足条件时，请找出最小的那个。

Format

Input

第一行一个正整数$T$，表示数据的组数。 接下来$T$行，每行$6$个整数$l,r,p,q,a,b$，意义如题所述。

Output

共$T$行，每行一个正整数，表示使位移大小$|y|$取最大值的$x$中最小的那个。

Samples

6
0 3 1 3 1 0
0 5 4 5 0 1
0 6 1 2 1 1
17 86 389 995 1 0
20 90 233 499 0 1
30 91 233 499 1 1

1
0
0
55
30
37

Limitation

对于30%的数据：$T\le5,r,q\le500$

对于50%的数据：$T\le5,r,q\le500000$

对于80%的数据：$T\le100$

对于90%的数据：$T\le300$

对于100%的数据：$T\le30000,0\le a,b\le1,ab≠0,0\le l\le r\le10^9,0\le p<q<5*10^8$

其中，对于前90%的数据，时间限制均为1秒。

Explanation

对于第一组数据，在$t$时刻的叠加波形为$y=\sin\frac{\pi x}{3}$，对于$x\in\{0,1,2,3\}$，可以看到$x\in\{1,2\}$时$|y|=\frac{\sqrt{3}}{2}$取到最大值，其中$x=1$为最小的满足条件的$x$。