using static System.Math;
using System;

public class Hello
{
    static void Main()
    {
        var q = int.Parse(Console.ReadLine().Trim());
        while (q-- > 0)
        {
            string[] line = Console.ReadLine().Trim().Split(' ');
            var n = int.Parse(line[0]);
            long k = int.Parse(line[1]);
            if (k == 1) Console.WriteLine(n - 1);
            else getAns(n, k);
        }
    }
    static void getAns(int n, long k)
    {
        long a = n * (k - 1);
        var p = Log10(a + 1) / Log10(k);
        Console.WriteLine((int)p);
    }
}