题目描述
给定两个正整数 nn 和 kk，你可以进行以下两种操作任意次（包括零次）：

选择一个整数 xx 满足 0≤x<k0≤x<k，将 nn 变为 k⋅n+xk⋅n+x。该操作每次花费 aa 枚金币。每次选择的整数 xx 可以不同。
将 nn 变为 ⌊nk⌋⌊nk⌋。该操作每次花费 bb 枚金币。其中 ⌊nk⌋⌊nk⌋ 表示小于等于 nknk 的最大整数。
给定正整数 mm，求将 nn 变为 mm 的倍数最少需要花费几枚金币。请注意：00 是任何正整数的倍数。

输入格式
第一行输入一个整数 TT表示测试数据组数。

对于每组测试数据，输入一行五个正整数 nn，kk，mm，aa，bb。

输出格式
每组数据输出一行一个整数，代表将 nn 变为 mm 的倍数最少需要花费几枚金币。如果无法完成该目标，输出 −1−1。

输入样例1
3
101 4 207 3 5
114 514 19 19 810
1 1 3 1 1
输出样例1
11
0
-1