import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] sa = br.readLine().split(" "); int q = Integer.parseInt(sa[0]); for (int i = 0; i < q; i++) { sa = br.readLine().split(" "); long a = Integer.parseInt(sa[0]); long b = Integer.parseInt(sa[1]); long c = Integer.parseInt(sa[2]); if (c == 1) { System.out.println(a * b); } else { long ans1 = 0; while (a >= c * c) { if (a % c > 0) { ans1++; } a /= c; ans1++; } ans1 *= b; long ans2 = Long.MAX_VALUE; for (int j = 0; j < 3; j++) { long x = (long) Math.pow(c, j); if (x > a) { break; } long val1 = j; long val2 = (a / x + c - 2) / (c - 1); long val3 = (a % x + c - 2) / (c - 1); long val = val1 + val2 + val3; val *= b; ans2 = Math.min(ans2, val); } System.out.println(ans1 + ans2); } } br.close(); } }