For each three prime numbers p_{1}, p_{2} and p_{3}, letis define Hamming sequence
H_{i}(p_{1}, p_{2}, p_{3}), i = 1,... as containing in increasing order all the natural numbers whose
only prime divisors are p_{1}, p_{2} or p_{3}.
For example, H(2, 3, 5) = 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27,...
So H_{5}(2, 3, 5)=6.

Input file format

In the single line of input file there are space-separated integers p_{1} p_{2} p_{3} i.

Output file format

The output file must contain the single integer - H_{i}(p_{1}, p_{2}, p_{3}).

Constraints

All numbers in input and output are less than 10^{18}.