Gaurav and Aayush are participating in the Tekken Tag Tournament of 20123. Of course, Dr. Sudarshan Iyengar has formed the rules of the fight.

There is a long horizontal line of infinite length with a center point P. Initially both Gaurav and Aayush will stand on the center P of the line facing each other. Don't worry, the line is thick enough to hold Aayush and Gaurav at the same place and at the same time. Gaurav can jump either A or B units to the left or right in one move. Aayush can jump either C or D units to the left or right in one move.

Dr. Sudarshan Iyengar wants to place exactly one "Health Potion" on the line such that both Gaurav and Aayush will be able to reach it independently in one or more moves. Also the "Health Potion" can be placed at most K units away from the center of the rope. Dr. Sudarshan Iyengar will let you watch the fight if you can decide the number of possible positions on the line to place the "Health Potion".

Input

First line contains T, the number of test cases. Each of the next T lines contains five positive integers, A B C D K.

1<=T<=1000

1<=A,B,C,D,K<=10^18

Output

For each test case, output on a newline, the number of possible positions to place the "Health Potion" on the line.

Example

Input:

3

2 4 3 6 7

1 2 4 5 1

10 12 3 9 16

Output:

3

3

5

Explanation:

For the second case,

Aayush jumps 2 units to the right and then 1 unit to the left. Gaurav jumps 5 units to the right and then 4 units to the left to reach 1 unit right from the center.

Aayush jumps 2 units to the left and then 1 unit to the right. Gaurav jumps 5 units to the left and then 4 units to the right to reach 1 unit left from the center.

"Health Potion" can also be placed at the center as players can reach it in 2 moves. Thus, there are three different positions at most 1 unit away from the center that are reachable by both the players in one or more moves.