题目描述

给定两个正整数 $n$ 和 $k$ ，你可以进行以下两种操作任意次（包括零次）：

选择一个整数 $x$ 满足 $0 \leq x < k$ ，将 $n$ 变为 $k\cdot n+x$ 。该操作每次花费 $a$ 枚金币。每次选择的整数 $x$ 可以不同。
将 $n$ 变为 $\lfloor \frac{n}{k} \rfloor$ 。该操作每次花费 $b$ 枚金币。其中 $\lfloor \frac{n}{k} \rfloor$ 表示小于等于 $\frac{n}{k}$ 的最大整数。

给定正整数 $m$ ，求将 $n$ 变为 $m$ 的倍数最少需要花费几枚金币。请注意： $0$ 是任何正整数的倍数。

输入格式

第一行输入一个整数 $T$ 表示测试数据组数。

对于每组测试数据，输入一行五个正整数 $n$ ， $k$ ， $m$ ， $a$ ， $b$ 。

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

3
101 4 207 3 5
114 514 19 19 810
1 1 3 1 1

11
0
-1

样例 $2$ 见下载文件

对于第一组样例数据，一开始 $n=101$ ，最优操作如下：

对于第二组样例数据，进行两次第二种操作将 $n$ 变为 $0$ 。共花费 $1 + 1 = 2$ 枚金币。

对于第三组样例数据，因为 $n = 114 = 6 \times 19$ 已经是 $m$ 的倍数，因此无需进行任何操作。共花费 $0$ 枚金币。

对于 $30\%$ 的数据， $n,k,m\leq 10$

对于 $60\%$ 的数据， $T\leq 1000, k,m\leq 10^3$

对于所有数据， $1\leq T\leq 10^5$ , $1\leq n\leq 10^{18}$ ， $1\leq k, m, a, b\leq 10^9$ 。