提示: 欢迎访问OurACM平台。
Problem 2125 简单的等式

Accept: 437    Submit: 1978
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

现在有一个等式如下:x^2+s(x,m)x-n=0。其中s(x,m)表示把x写成m进制时,每个位数相加的和。现在,在给定n,m的情况下,求出满足等式的最小的正整数x。如果不存在,请输出-1。

Input

有T组测试数据。以下有T(T<=100)行,每行代表一组测试数据。每个测试数据有n(1<=n<=10^18),m(2<=m<=16)。

Output

输出T行,有1个数字,满足等式的最小的正整数x。如果不存在,请输出-1。

Sample Input

4 4 10 110 10 15 2 432 13

Sample Output

-1 10 3 18

Source

福州大学第十届程序设计竞赛

Submit  Back  Status  Discuss