$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 \leq T \leq 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 \leq \ N \leq 10^{12}; 1 \leq K \leq 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 \leq N \leq 10^6; 1 \leq K \leq 50$.
• Subtask $2$ ($50 \%$): $10^6 \leq N \leq 10^{12}; 1 \leq K \leq 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 \geq 1447$.