Greatest Dumpling Fight

All submissions for this problem are available.
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.
Author:  rosyish 
Tester:  laycurse 
Editorial  http://discuss.codechef.com/problems/DUMPLING 
Tags  april12 easy rosyish 
Date Added:  3032012 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.4, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions