#F. Simple Harmonic Vibration

    Type: Default 1000~3000ms 512MiB

Simple Harmonic Vibration

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

The problem is not very easy.

Description

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

你将会被给定两列简谐波:如果只有第一列简谐波,那么在tt时刻这列简谐波的波形为y=asinπpxqy=a\sin\frac{\pi px}{q};如果只有第二列简谐波,那么在tt时刻这列简谐波的波形为y=bcosπpxqy=b\cos\frac{\pi px}{q}

现在你看到的是将这两列简谐波在tt时刻叠加(可以理解为代数和)的照片,即波形y=asinπpxq+bcosπpxqy=a\sin\frac{\pi px}{q}+b\cos\frac{\pi px}{q}

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

Format

Input

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

Output

TT行,每行一个正整数,表示使位移大小y|y|取最大值的xx中最小的那个。

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%的数据:T5,r,q500T\le5,r,q\le500

对于50%的数据:T5,r,q500000T\le5,r,q\le500000

对于80%的数据:T100T\le100

对于90%的数据:T300T\le300

对于100%的数据:T30000,0a,b1,ab0,0lr109,0p<q<5108T\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

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