You are given an integer n and an integer k.

In one step you can do one of the following moves: 

  * decrease n by 1; 
  * divide n by k if n is divisible by k. 



For example, if n = 27 and k = 3 you can do the following steps: 27 → 26 → 25 → 24 → 8 → 7 → 6 → 2 → 1 → 0.

You are asked to calculate the minimum number of steps to reach 0 from n. 

Input

The first line contains one integer t (1 ≤ t ≤ 100) — the number of queries.

The only line of each query contains two integers n and k (1 ≤ n ≤ 10^{18}, 2 ≤ k ≤ 10^{18}).

Output

For each query print the minimum number of steps to reach 0 from n in single line. 

Example

Input


2
59 3
1000000000000000000 10


Output


8
19

Note

Steps for the first test case are: 59 → 58 → 57 → 19 → 18 → 6 → 2 → 1 → 0.

In the second test case you have to divide n by k 18 times and then decrease n by 1.
	import java.io.*;
	import java.util.*;

	public class Task {
		static final StdIn in = new StdIn();
		static final PrintWriter out = new PrintWriter(System.out);

		public static void main(String[] args) {
			int t = in.nextInt();
			
			while(t-- > 0) {
				long n = in.nextLong();
				long k = in.nextLong();
				long count = 0;
				while(n > 0) {
					if(n%k == 0) {
						n /= k;
						count++;
					} else {
						long p = n%k;
						n -= p;
						count += p;
					}
					
				}
				out.println(count);
			}
			
			
			
			out.println();
			out.close();

		}

		public static boolean isEven(int num) {
			if(num%2 == 0) {
				return true;
			} else {
				return false;
			}
		}


		static class Rating {
			int before;
			int after;
		}
		
		static class Pair1 {
			long first;
			long second;
		}

		static void swap(int a, int b) {
			int temp = a;
			a = b;
			b = temp;
		}

		public static ArrayList<Integer> reverseArrayList(ArrayList<Integer> alist) 
		{ 
			// Arraylist for storing reversed elements 
			// this.revArrayList = alist; 
			for (int i = 0; i < alist.size() / 2; i++) { 
				Integer temp = alist.get(i); 
				alist.set(i, alist.get(alist.size() - i - 1)); 
				alist.set(alist.size() - i - 1, temp); 
			} 
	
			// Return the reversed arraylist 
			return alist; 
		} 

		static class Pair {
			int first = 1;
			int second = 2;
		}

		public void fibonacci(int N) {
			boolean arr[] = new boolean[N];
			Arrays.fill(arr, false);
			arr[0] = true;
			if(N>1)
				arr[1] = true;

			Pair p = new Pair();
			for (int i = 3; i <= N; i++) {
				
				if(p.first + p.second == i) {
					arr[i-1] = true;
					p.first = p.second;
					p.second = i;
				} else {
					arr[i-1] = false;
				}
			}
		}

		public class Solver {
			Solver() {
				
			}
			
		}

		static long factorial(long x) {
			if(x <= 1) {
				return 1;
			}
			long res = 2;
			for (int i = 3; i <= x; i++) {
				res = res * i;
			}
			return res;
		}
		
		static long gcdOfFactorial(long a, long b) { 
			if (b == 0) 
				return a; 
			return gcdOfFactorial(b, a % b);
		} 
		
		static class StdIn {
			final private int BUFFER_SIZE = 1 << 16;
			private DataInputStream din;
			private byte[] buffer;
			private int bufferPointer, bytesRead;
			public StdIn() {
				din = new DataInputStream(System.in);
				buffer = new byte[BUFFER_SIZE];
				bufferPointer = bytesRead = 0;
			}
			public StdIn(InputStream in) {
				try{
					din = new DataInputStream(in);
				} catch(Exception e) {
					throw new RuntimeException();
				}
				buffer = new byte[BUFFER_SIZE];
				bufferPointer = bytesRead = 0;
			}
			public String next() {
				int c;
				while((c=read())!=-1&&(c==' '||c=='\n'||c=='\r'));
				StringBuilder s = new StringBuilder();
				while (c != -1)
				{
					if (c == ' ' || c == '\n'||c=='\r')
						break;
					s.append((char)c);
					c=read();
				}
				return s.toString();
			}
			public String nextLine() {
				int c;
				while((c=read())!=-1&&(c==' '||c=='\n'||c=='\r'));
				StringBuilder s = new StringBuilder();
				while (c != -1)
				{
					if (c == '\n'||c=='\r')
						break;
					s.append((char)c);
					c = read();
				}
				return s.toString();
			}
			public int nextInt() {
				int ret = 0;
				byte c = read();
				while (c <= ' ')
					c = read();
				boolean neg = (c == '-');
				if (neg)
					c = read();
				do
					ret = ret * 10 + c - '0';
				while ((c = read()) >= '0' && c <= '9');

				if (neg)
					return -ret;
				return ret;
			}
			public int[] readIntArray(int n, int os) {
				int[] ar = new int[n];
				for(int i=0; i<n; ++i)
					ar[i]=nextInt()+os;
				return ar;
			}
			public long nextLong() {
				long ret = 0;
				byte c = read();
				while (c <= ' ')
					c = read();
				boolean neg = (c == '-');
				if (neg)
					c = read();
				do
					ret = ret * 10 + c - '0';
				while ((c = read()) >= '0' && c <= '9');
				if (neg)
					return -ret;
				return ret;
			}
			public long[] readLongArray(int n, long os) {
				long[] ar = new long[n];
				for(int i=0; i<n; ++i)
					ar[i]=nextLong()+os;
				return ar;
			}
			public double nextDouble() {
				double ret = 0, div = 1;
				byte c = read();
				while (c <= ' ')
					c = read();
				boolean neg = (c == '-');
				if (neg)
					c = read();
				do
					ret = ret * 10 + c - '0';
				while ((c = read()) >= '0' && c <= '9');
				if (c == '.')
					while ((c = read()) >= '0' && c <= '9')
						ret += (c - '0') / (div *= 10);
				if (neg)
					return -ret;
				return ret;
			}
			private void fillBuffer() throws IOException {
				bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
				if (bytesRead == -1)
					buffer[0] = -1;
			}
			private byte read() {
				try{
					if (bufferPointer == bytesRead)
						fillBuffer();
					return buffer[bufferPointer++];
				} catch(IOException e) {
					throw new RuntimeException();
				}
			}
			public void close() throws IOException {
				if (din == null)
					return;
				din.close();
			}
		}
	}