Greatest Dumpling Fight

Problem code: DUMPLING

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
Date Added: 3-03-2012
Time Limit: 1 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

@admin : is it required that

gn13 @ 2 Apr 2012 10:41 PM
@admin : is it required that both should reach at dumpling in equal moves?

@fenix Please don't say about

hiroto_adm @ 3 Apr 2012 10:58 AM
@fenix Please don't say about your accepted code during the contest.

@gn13 No. The number of

hiroto_adm @ 3 Apr 2012 11:04 AM
@gn13 No. The number of Shifu's move can be differ from one of Po's.

@rushilpaul We cannot give

hiroto_adm @ 3 Apr 2012 11:05 AM
@rushilpaul We cannot give you any hint during the contest. Please don't ask. Anyway your solution got Time Limit Exceeded.

@almighty We cannot give you

hiroto_adm @ 3 Apr 2012 11:06 AM
@almighty We cannot give you any hint during the contest.

@admin : "Dumpling can also

swaprocks123 @ 3 Apr 2012 02:58 PM
@admin : "Dumpling can also be placed at the center as a chef can reach it in 2 moves." Please Explain this. How can chef reach the center in two moves....???

@swaprocks123 It is simple to

isha_adm @ 3 Apr 2012 06:40 PM
@swaprocks123 It is simple to see that, say, Chef Shifu jumps distance A towards the right and then distance A towards left.

@max969 Many have already

isha_adm @ 3 Apr 2012 06:44 PM
@max969 Many have already solved this problem. Sample test cases are enough.

@isha_adm , but shifu can't

rohanag @ 3 Apr 2012 06:48 PM
@isha_adm , but shifu can't jump distance A to the right? Isn't he allowed to only jump distance B to the right, and A to the left? So he needs to go 2*A to the left, then B to the right?? Making the total number of moves 3 to land in the center. am i wrong?

@rohanag Chef Shifu can jump

isha_adm @ 3 Apr 2012 06:52 PM
@rohanag Chef Shifu can jump A or B units at a time. They can be made to the left or to the right as he wishes. Similarly for Chef Po. Hope this clears your doubt.

For last explaination of

karora @ 4 Apr 2012 02:46 AM
For last explaination of placing at center, there can be infinite cases as both can make 2, 4, 6, 8,... and so on moves.

@rushilpaul many people have

isha_adm @ 4 Apr 2012 11:42 AM
@rushilpaul many people have already submitted the solution successfully. The time limits are fine.

@kq_viet Please don't post

isha_adm @ 4 Apr 2012 06:43 PM
@kq_viet Please don't post your approaches. You will have to figure out the solution on your own. @ankit2601 As already mentioned, the sample tests are enough. Thinking about other test cases is part of solving the problem.

@chaubey12 You should read

isha_adm @ 4 Apr 2012 06:46 PM
@chaubey12 You should read the problem statement clearly to figure this out. The explanation of the second case is enough to answer your question

python 2.5 and 3.0 but no 2.6

foofoo @ 4 Apr 2012 11:04 PM
python 2.5 and 3.0 but no 2.6 wha???

python 2.5 works fyn for your

slayer_x @ 4 Apr 2012 11:47 PM
python 2.5 works fyn for your 2.6 code...There are minor differences but wont really matter much.

@nishant240390, nightwarex ,

isha_adm @ 6 Apr 2012 03:48 PM
@nishant240390, nightwarex , chaubey12 - no, we cannot discuss the solution till the contest ends. @listlion - Do not discuss the complexity of your approach in the comments. Determining the complexity is part of solving the problem.

@prad1prad0073 Wait for the

isha_adm @ 8 Apr 2012 10:53 AM
@prad1prad0073 Wait for the contest to end. Any such requests through email to codechef admins.

@hellodear All information

isha_adm @ 8 Apr 2012 10:55 AM
@hellodear All information about the test cases is provided in the problem description.

@all Kindly refrain from

isha_adm @ 9 Apr 2012 02:25 PM
@all Kindly refrain from asking hints here. If you can't solve it, wait for the contest to end when the editorial will be posted. @nj4niraj Time limit is 1s per test file.

Is der different time limits

deadzg_devil @ 10 Apr 2012 11:50 AM
Is der different time limits for different languages?? If so den how much it is for Perl??

@deadzg_devil You can find

isha_adm @ 10 Apr 2012 04:08 PM
@deadzg_devil You can find out about time limits about different language here http://blog.codechef.com/2009/04/01/announcing-time-limits-based-on-prog...

please tell me where my

flingo_1992 @ 11 Apr 2012 07:54 PM
please tell me where my solution is wrong link: http://www.codechef.com/viewsolution/943198

@isha_adm :

adityamurgai @ 11 Apr 2012 11:12 PM
@isha_adm : http://www.codechef.com/viewsolution/968624 , this is the link to the solution that i had submitted while the contest was on, which returned a WA......now since everyone's solutions are public i went through a couple of the correct submitted ones and found that i indeed had used the exact and the correct algo.....i can hardly make out what did me wrong....please help me to bring it to my notice

@adityamurgai: When you

oldmonk @ 24 Apr 2012 04:38 PM
@adityamurgai: When you multiply two unsigned long long it will overflow and exceeds 10^18. This is possible for the following input case A=B=10^18. C=D=10^18. Both the GCD will be 10^18. Hence when multiplied there is a overflow and gives wrong results.

SUCCESSFUL SUBMISSIONS


Fetching successful submissions