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.*; 
import javafx.util.Pair; 

public class TaskA_june5 
{ 

/*
 *   ********   *******    ******** 	
 *   *          *    *           *
 *   *          *   *           * 
 *   *          * *            *
 *   *          *   *         *
 *   ********   *    *       *
 */
	static	Reader in=new Reader();
	static Scanner sc=new Scanner(System.in);
	public static void main(String[] args) throws IOException 
	{ 
		int test=in.integer();
		for(int it=0;it<test;it++) {
			long n=in._long();
			long k=in._long();
			long c=0;
			while(n>=k) {
				
				c+=n%k;
				n=n/k;
				c++;
			}
			c+=n%k;
			System.out.println(c);
		}
	}

 static int partition(Pair<Integer,Integer> arr[], int low, int high) 
    { 
        int pivot = arr[high].getKey();  
        int i = (low-1);
        for (int j=low; j<high; j++) 
        {  
            if (arr[j].getKey() <= pivot) 
            { 
                i++;
                Pair<Integer,Integer> temp = arr[i]; 
                arr[i] = arr[j]; 
                arr[j] = temp; 
            } 
        }
        Pair<Integer,Integer> temp = arr[i+1]; 
        arr[i+1] = arr[high]; 
        arr[high] = temp; 
  
        return i+1; 
    } 
   static void sort(Pair<Integer,Integer> arr[], int low, int high) 
    { 
        if (low < high) 
        { 
            int pi = partition(arr, low, high); 
            sort(arr, low, pi-1); 
            sort(arr, pi+1, high); 
        } 
    }
	/*
	 * seach algorithm
	 */
	static int return_greater_index(int arr[],int start,int end,int x)
	{
		int ans=-1;
		int mid;
		while(start<=end) {
			 mid=(start+end)/2;
			if(arr[mid]<=x)
				start=mid+1;
			else 
				{
				ans=mid;
				end=mid-1;
				}
		}
		return ans;
	}
public static int lowerBound(int[] a, int v)
	{
		int low = -1, high = a.length;
		while(high-low > 1){
			int h = high+low>>>1;
			if(a[h] >= v){
				high = h;
			}else{
				low = h;
			}
		}
		return high;
	}
static int return_lower_index(int arr[],int start,int end,int x)
	{
		int ans=-1;
		int mid;
		while(start<=end) {
			 mid=(start+end)/2;
			if(arr[mid]<=x) {
				ans=mid;
				start=mid+1;
			}
			else 
				{
				end=mid-1;
				}
		}
		return ans;
	}
	/*
	 * pairs of <int,int> <double,double>
	 */
	static Pair<Integer,Integer> pair(int x,int y){
		Pair<Integer,Integer> p=new Pair<Integer, Integer>(x,y);
		return p;
	}
	static Pair<Double,Double> pair(double x,double y){
		Pair<Double,Double> p=new Pair<Double,Double>(x,y);
		return p;
	}
	/*
	 * for loop
	 */
static void rep(int arr[]) throws IOException {
	int n=arr.length;
	for(int i=0;i<n;i++)
		arr[i]=in.integer();
}
	/*display 
	 array
	 */
	static void display(Integer arr[][],int x,int y) {
		for(int i=0;i<x;i++) {
			for(int j=0;j<y;j++)
			{
				System.out.print(arr[i][j]+" ");
			}
			System.out.println();
		}
	}
	static void display(Integer arr[]) {
		int x=arr.length;
			for(int j=0;j<x;j++)
			{
				System.out.print(arr[j]+" ");
			}
			System.out.println();
	}
	
	/*
	 * input 
	 */
	
	static class Reader 
	{ 
		final private int BUFFER_SIZE = 1 << 16; 
		private DataInputStream din; 
		private byte[] buffer; 
		private int bufferPointer, bytesRead; 

		public Reader() 
		{ 
			din = new DataInputStream(System.in); 
			buffer = new byte[BUFFER_SIZE]; 
			bufferPointer = bytesRead = 0; 
		} 

		public Reader(String file_name) throws IOException 
		{ 
			din = new DataInputStream(new FileInputStream(file_name)); 
			buffer = new byte[BUFFER_SIZE]; 
			bufferPointer = bytesRead = 0; 
		} 

		public String string() throws IOException 
		{ 
			byte[] buf = new byte[64]; // line length 
			int cnt = 0, c; 
			while ((c = read()) != -1) 
			{ 
				if (c == '\n') 
					break; 
				buf[cnt++] = (byte) c; 
			} 
			return new String(buf, 0, cnt); 
		} 

		public int integer() throws IOException 
		{ 
			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 long _long() throws IOException 
		{ 
			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 double _double() throws IOException 
		{ 
			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() throws IOException 
		{ 
			if (bufferPointer == bytesRead) 
				fillBuffer(); 
			return buffer[bufferPointer++]; 
		} 

		public void close() throws IOException 
		{ 
			if (din == null) 
				return; 
			din.close(); 
		} 
	} 

} 
