该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小S特别喜欢数论，最近正在研究埃式筛法。他发现在这个筛法的过程中，需要去枚举质数的倍数 根据唯一分解定理，任何合数都可以表示为若干质数的乘积形式，于是可以筛掉所有的合数，找出质数。 在这个过程中，他想要解决的一个子问题，就是如何找到第一个大于等于L且小于等于R的p的倍数。这个 问题并不复杂，小S一会就想到了枚举的方法，但是他在想一个更难的问题。 如何找到在[L,R]范围内(包括端点)p的第k小的倍数 ？ 当然如果不存在这个数字，你应该告诉小S结果为-1。 例如，p = 2 ，[10 , 20]的范围内 10,12,14,16,18,20都是p的倍数，第5小的倍数为18。

输入描述

每个问题包括 $T$ 组数据，每组数据包含四个正整数 $L$ , $R$ , $p$ ，$k$ 每个数字的含义由题目描述中所知。

输出描述

输出一个正整数，表示在[L,R]范围内(包括端点),p的第k小的倍数。 若不存在，则输出一行 "-1"(不包含双引号)。

样例描述

输入1 3 10 20 2 5 1 100 3 10 80 82 3 2

输出1 18 30 -1

样例解释

第一组描述见题意描述中。

第二组数据中，1 - 100 中3的倍数有 3 6 9 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54 57 60 63 66 69 72 75 78 81 84 87 90 93 96 99 其中第10个倍数是30。

第三组数据中，80 - 82 中3的倍数只有 81。

数据范围描述

30%的数据保证，所有出现的数字，在1000范围内。 另外20%的数据保证，k = 1。 100%的数据范围保证，$T \le 10^5$ , $1 \le L \le 10^9$ , $1\le R\le 10^{9}$ , $1\le p\le 10^{9}$ , $1\le k\le 10^{9}$ 。