描述

对于每三个质数$p_1$、$p_2$和$p_3$，我们定义汉明序列$H_i(p_1, p_2, p_3)$，其中$i = 1, \ldots$ ，该序列按递增顺序包含所有其唯一质因数为$p_1$、$p_2$或$p_3$的自然数。

例如，$H(2, 3, 5) = 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, \ldots$ 。

所以$H_5(2, 3, 5)=6$。

输入

在输入文件的单独一行中，有以空格分隔的整数$p_1$ $p_2$ $p_3$ $i$。

输出

输出文件必须包含单独一个整数，即$H_i(p_1, p_2, p_3)$的值。输入和输出中的所有数字都小于$10^{18}$。

输入数据 1

7 13 19 100

输出数据 1

26590291

来源

$2000$年东北欧地区赛，远东分区赛