题目描述

给定一个等差数列，第一项是 a , 从第二项开始，每项与前一项的差都是一个定值 b 。如果用数学形式来表示，那么可以表示成 a+b×x , 其中 x≧0 ，且是整数。例如： a=1, b=2, 那么这个等差数列就是：1，3，5，7，9 ......

再给定一个等比数列，第一项是 c , 从第二项开始，每项是前一项的 d 倍。如果用数学形式来表示等比数列，则是 c×$d^y$ 。 其中 y≧0, 且是整数。例如： c = 2, d = 3, 那么这个等比数列就是：2，6，18，54 ......

你的任务是计算在 1 至 upperBound 内的正整数，有多少正整数是“合法”的？

所谓的“合法”是指：该整数属于上面给定的等差数列的某项或者属于等比数列的某项，或者既属于等差数列的项也属于等比数列的项。

输入格式

一行，5 个整数，分别是a，b，c，d，upperBound ( 1 ≤ a , b , c , upperBound ≤ $10^{12}$ , 1 ≤ d ≤ $10^5$ ）

对于 80% 的数据，1 ≤ upperBound ≤ 1000000 。

输出格式

一个整数，表示“合法”正整数的个数。

样例

1 1 1 2 1000

1000

3 3 1 2 1000

343

452 24 4 5 600

10