$Neko$ vốn là một học sinh không có hứng thú gì nhiều với môn Toán, nhưng mọi chuyện đã thay đổi từ khi $Neko$ crush $Capoo$, một bạn mèo học chuyên Toán.

Hôm nay $Neko$ đang được học về phép toán lũy thừa. Với bản tính không thích sự cứng nhắc của các định lý cậu phải học trong môn Toán, $Neko$ thường tự sáng tạo ra các định nghĩa mới cho các con số. Trong giờ học hôm nay, khi đang nhớ thương về crush của mình, $Neko$ đã đặt ra một định nghĩa mới: số "cute". Biết một số được xem là "cute" khi nó được tạo thành từ tổng của các lũy thừa bậc $i$ ($i\in 0,1,2,\dots$) cơ số $K$.

Trong lúc $Neko$ chưa kịp tìm ra số "cute" nhỏ nhất lớn hơn bằng số $N$ thì cậu đã bị thầy giáo gọi lên bảng làm bài. Vì thế bạn hãy giúp $Neko$ tìm ra những số "cute" như crush của cậu ấy nhé!

Dữ liệu vào

• Dòng đầu tiên chứa số $T$ ($1\le T\le 100$) là số testcase của bài toán.
• $T$ dòng tiếp theo ứng với $T$ testcase, mỗi dòng chứa $2$ số nguyên dương $N$ và $K$ ($1\le N\le {10}^{12};1\le K\le 100$).

Kết quả ra

• Gồm $T$ dòng, mỗi dòng chứa $2$ số nguyên dương $A,B$ lần lượt là bậc của số hạng cuối cùng trong dãy tổng các lũy thừa cơ số $K$ và tổng các số hạng trong dãy ứng với testcase tương ứng.

Ràng buộc

• Subtask $1$ ($50\%$): $1\le N\le {10}^6;1\le K\le 50$.
• Subtask $2$ ($50\%$): ${10}^6\le N\le {10}^{12};1\le K\le 100$.

Ví dụ

Dữ liệu

1
1447 3

Kết quả

7 3280

Giải thích

Ta có: $3^0+3^1+3^2+3^3+3^4+3^5+3^6+3^7=3280\ge 1447$.