Barry Allen is a police scientist (his job title was changed to a forensic scientist in The Flash: Iron Heights one-shot) with a reputation for being very slow, and frequently late, which frustrates his fiancee, Iris West, as the result of being absent-minded and his devotion to crime-solving. One night, as he is working late, a lightning bolt shatters a case full of chemicals and spills all over Barry. As a result, Allen finds that he can run extremely fast and has matching reflexes and senses. He dons a set of red tights sporting a lightning bolt (reminiscent of the original Fawcett Comics Captain Marvel), dubs himself the Flash (after his childhood comic book hero, Jay Garrick), and becomes Central City's resident costumed crimefighter. Central City University professor Ira West (Iris' adoptive father) designed Allen's costume and the ring which stores it while Allen is in his civilian identity. The ring can eject the compressed clothing when Allen needs it and suck it back in with the aid of a special gas that shrinks the suit. In addition, Allen invented the cosmic treadmill, a device that allowed for precise time travel and was used in many stories. Allen was so well liked that nearly all speedsters that come after him are often compared to him. Batman once said "Barry is the kind of man that I would've hoped to become if my parents had not been murdered."

Somehow, Barry lost his superspeed for some days so he is very upset.. He is alike simple men like us. At mid-night he goes to the rooftop of star-labs and looking to the sky.. He realized his eye sight is decreased to 45 degree left and 45 degree right only.. The moon is full and Barry loved to look at the moon. The moon is moving constantly from left to right with a constant velocity in a straight line. Barry wants to see the moon as much time as possible, so he needs to move.

Consider the whole scenario in 2D.. that means, Barry and the moon on a 2D plane

Given the coordinates of the position of Barry where Barry is on the x axis (at (x,0) point) … and the coordinate of the moon and the velocity of the moon, you need to calculate the displacement of Barry so that he can see the moon for certain given time.

Consider at the starting point Barry can see the moon…

Input

The first line contains one integer N (1 <= N <= 10^5) denoting the number of test cases. Then N lines follows.

Each line containing five integers x, p, q, T and v:

• x (-10^5 <= x <= 10^5): the coordinate of Barry with respect to x axis
• T (1 <= T <= 10^3): the time Barry wants to see the moon
• (p,q) (-10^5 <= p <= 10^5, 1 <= q <= 10^5): the coordinate of the moon
• v (1 <= v <= 10^2): the velocity of the moon

Output

Just print the total displacement of Barry if he wants to see the moon for T unit time for each test case.

Example

Input

2
5 5 6 5 2
0 1 1 5 1

Output

4
5