using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
//using System.Text;
//using System.Threading.Tasks;
using System.IO;
using System.Runtime.CompilerServices;
////using System.Web.UI;
//using Debug = System.Diagnostics.Debug;
//// using System.Drawing.Primitives;
////using System.Drawing;
//using System.Windows;
using System.Numerics;

namespace ConsoleApp1
{
    class Program 
    {
        static void Main(string[] args)
        {
            new Solver().Solve();
        }
    }

    class GeneralPurposeClass {
        //public const double inf = double.PositiveInfinity;
        public const long inf = 1L << 50;
        public static readonly TextWriter error = Console.Error;
        public static Random random = new Random();

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static void Rep(long n_, Action<long> action)
        {
            for (long i = 0; i < n_; i++)
            {
                action(i);
            }
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static void Rep2(int a, long n_, Action<long> action)
        {
            for (long i = a; i < n_; i++)
            {
                action(i);
            }
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static void Rrep(long n_, Action<long> action)
        {
            for (long i = n_; i > -1; i--)
            {
                action(i);
            }
        }

        public static void TestReps()
        {
            var end = 3;
            var end2 = 10;
            error.WriteLine("rep ------");
            Dumpl("end", end);
            Rep(end, (i) =>
            {
                error.WriteLine(i);
            });

            error.WriteLine("");
            error.WriteLine("rep2 ------");
            var start = 7;
            Dumpl("start", start);
            Dumpl("end2", end2);
            Rep2(start, end2, (i) =>
            {
                error.WriteLine(i);
            });

            error.WriteLine("");
            error.WriteLine("rrep ------");
            Dumpl("end", end);
            Rrep(end, (i) =>
            {
                error.WriteLine(i);
            });
        }

        public static string ReadLine()
        {
            var s = Console.ReadLine();
            Dumpl("s", s);
            if (s.Length == 0) s = Console.ReadLine();
            var c = s[0];
            if (c == ' ' || c == '\n' || c == '\r') s = ReadLine();
            Dumpl("s", s);

            return s;
        }

        public static string ReadNext()
        {
            var s = "";
            while (true)
            {
                var c = Console.Read();
                if (c != ' ' && c != '\n' && c != '\r')
                {
                    s += (char)c;
                    break;
                }
            }
            while (true)
            {
                var c = Console.Read();
                if (c == ' ' || c == '\n' || c == '\r') break;
                s += (char)c;
            }
            return s;
        }

        public static long ReadLong()
        {
            return Stol(ReadNext());
        }

        public static long Stol(string s)
        {
            return long.Parse(s);
        }

        public static void Write<T>(T a)
            where T : IComparable
        { Console.Write(a); }

        public static void WriteL<T>(T a)
            where T : IComparable
        { Console.WriteLine(a); }

        public static void Dump<T>(string s, T a)
            where T : IComparable
        {
#if DEBUG
            error.Write(s + ": " + a.ToString() + ' ');
#endif
        }

        public static void Dumpl<T>(string s, T a)
            where T : IComparable
        {
#if DEBUG
            Dump(s, a); error.WriteLine();
#endif
        }

        public int PowRandom(int a)
        {
            double nextDouble = NextDouble(a);
            return PowAndFloor(nextDouble);
        }

        public int PowAndFloor(double a)
        {
            return (int)Math.Floor(Math.Pow(10, a));
        }

        public double NextDouble(int a)
        {
            return random.NextDouble() * a;
        }

        public double NextDouble(double a)
        {
            return random.NextDouble() * a;
        }

        public void WriteForMakeSampleCase<T>(T a)
            where T : IComparable
        {
#if DEBUG
            return;
#endif
            WriteL(a);
        }
    }

    class Solver : GeneralPurposeClass
    {
        long n, k;

        long Ans()
        {
            if (k == 1) return n - 1;
            else
            {
                var cur = 0L;
                var cur2 = 1L;
                var ans = -1;
                while (cur < n)
                {
                    cur += cur2;
                    cur2 *= k;
                    ans++;
                }
                return ans;
            }
        }


        public void Solve()
        {
            var q = ReadLong();

            Rep(q, (i) =>
            {
                n = ReadLong();
                k = ReadLong();

                WriteL(Ans());
            });

        }
    }
}