Chef Shifu and Chef Po are participating in the Greatest Dumpling Fight of 2012.
Of course, Masterchef Oogway has formed the rules of the fight.

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

Masterchef Oogway wants to place exactly one dumpling on the rope such that
both Chef Shifu and Chef Po will be able to reach it independently in one or more moves.
Also the dumpling can be placed at most K units away from the center of the rope.
Masterchef Oogway will let you watch the fight if you can decide the number of possible positions on the rope to place the dumpling.

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 dumpling on the rope.

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,

Chef Po jumps 2 units to the right and then 1 unit to the left.
Chef Shifu jumps 5 units to the right and then 4 units to the left
to reach 1 unit right from the center.

Chef Po jumps 2 units to the left and then 1 unit to the right.
Chef Shifu jumps 5 units to the left and then 4 units to the right
to reach 1 unit left from the center.

Dumpling can also be placed at the center as a chef 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 chefs in one or more moves.

见题面

见题面