题目描述

著名的“第二食物”商店一个月只卖两天杂货。而且每一天的价格都不一样。你一个月想买n公斤土豆。你知道在这个月的第一天，1公斤土豆的价格是a个硬币，第二天是b个硬币。在“第二食物”中，你可以买到任意整公斤的土豆。

幸运的是，“第二食物”宣布了土豆的促销活动，只在每月的第一天有效-你每买m公斤土豆，就可以得到1公斤作为礼物!也就是说，每购买m公斤，就可以获得m+1公斤。

求出购买至少n公斤土豆所需的最小硬币数。

输入

每个测试包含多个测试用例。

第一行包含测试用例的数量t(1≤t≤10000)。

测试用例的描述如下。

每个测试用例的第一行包含两个整数a和b (1< a, b < 10^9)——分别是第一天和第二天1公斤土豆的价格。

第二行包含两个整数n和m (1 < n, m≤10^9)——需要购买的土豆数量和使用促销活动的土豆数量。

输出

对于每个测试用例，打印一个整数——购买至少n公斤土豆所需要支付的最小硬币数量。

5
5 4
3 1
5 4
3 2
3 4
3 5
20 15
10 2
1000000000 900000000
1000000000 8

9
10
9
135
888888888900000000

Note

请注意在第一个测试案例中，在第一天，你购买1公斤，并获得1公斤的促销。第二天，你可以买1公斤土豆。因此，你总共将花费5+4=9个硬币。

在第二个测试案例中，在第一天你买了2公斤，并获得了另一个1公斤的促销。这样你将花费2个5=10个硬币。