Problem: There is an infinite set generated as follows:

  * 1 is in this set. 
  * If x is in this set, x ⋅ a and x+b both are in this set. 



For example, when a=3 and b=6, the five smallest elements of the set are:

  * 1, 
  * 3 (1 is in this set, so 1⋅ a=3 is in this set), 
  * 7 (1 is in this set, so 1+b=7 is in this set), 
  * 9 (3 is in this set, so 3⋅ a=9 is in this set), 
  * 13 (7 is in this set, so 7+b=13 is in this set). 



Given positive integers a, b, n, determine if n is in this set.

Input

The input consists of multiple test cases. The first line contains an integer t (1≤ t≤ 10^5) — the number of test cases. The description of the test cases follows.

The only line describing each test case contains three integers n, a, b (1≤ n,a,b≤ 10^9) separated by a single space.

Output

For each test case, print "Yes" if n is in this set, and "No" otherwise. You can print each letter in any case.

Example

Input


5
24 3 5
10 3 6
2345 1 4
19260817 394 485
19260817 233 264


Output


Yes
No
Yes
No
Yes

Note

In the first test case, 24 is generated as follows:

  * 1 is in this set, so 3 and 6 are in this set; 
  * 3 is in this set, so 9 and 8 are in this set; 
  * 8 is in this set, so 24 and 13 are in this set. 



Thus we can see 24 is in this set.

The five smallest elements of the set in the second test case is described in statements. We can see that 10 isn't among them.

Solution (in JAVA):

Solution:

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.ObjectInputStream.GetField;
import java.lang.reflect.Array;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

import javax.sound.sampled.ReverbType;


public class N729 {
	static PrintWriter out;
	static Scanner sc;
	static ArrayList<int[]>q,w,x;
	static ArrayList<Integer>adj[];
	static HashSet<Integer>primesH;
	static boolean prime[];
	//static ArrayList<Integer>a;
	static HashSet<Long>tmp;
	static int[][][]dist;
	static boolean[]v;
	static int[]a,b,c,d;
	static Boolean[][]dp;
	static char[][]mp;
	static int A,B,n,m,h,ans,sum;
	//static String a,b;
	static long oo=(long)1e9+7;
	public static void main(String[]args) throws IOException {
		sc=new Scanner(System.in);
		out=new PrintWriter(System.out);
		//A();
		B();
		//C2();
		//C();
		//D();
		//E();
		//out.println(10000);
		//for(int i=0;i<10000;i++)out.println((int)1e9);
		//F();
		//G();
		out.close();
	}
	  private static void A() throws IOException {
		  int t=ni();
		  while(t-->0) {
			 int n=ni();
			 a=nai(2*n);
			 int odd=0;
			 for(int i=0;i<2*n;i++) {
				 if(a[i]%2==1)odd++;
			 }
			 out.println(odd==n?"YES":"NO");
		  }
	  }
	  static long[] gcdExtended(long p, long q) {
		      if (q == 0)
		         return new long[] { p, 1, 0 };

		      long[] vals = gcdExtended(q, p % q);
		      long d = vals[0];
		      long a = vals[2];
		      long b = vals[1] - (p / q) * vals[2];
		      return new long [] { d, a, b };
	  }
		static PriorityQueue<String>pq;
		static void B() throws IOException {
			int t=ni();
			a:while(t-->0) {
				int n=ni(),a=ni(),b=ni();
				long cur=1l;
				while(cur<=n) {
					if((n-cur)%b==0) {ol("yes");continue a;}
					if(a==1)break;
					cur*=a;
				}
				ol("no");
			}
		}

		static void C() throws IOException{
			 int t=ni();
			 while(t-->0) {
				 long n=nl();
//				 long odd=(n/2l)%oo;
//				 if(n%2==1)odd++;
//				 long evthrees=(n/6l)%oo;
//				 long ans=(2l*odd)%oo;
//				 long four=evthrees/2l;
//				 long five=evthrees/2l;
//				 if(evthrees%2==1)four++;
//				 ans=(ans+(4l*four)%oo)%oo;
//				 ans=(ans+(5l*five)%oo)%oo;
//				 long rem=(n-odd-evthrees+oo)%oo;
//				 ans=(ans+(3l*rem)%oo)%oo;
				 
				 long odd=n/2l;
				 if(n%2==1)odd++;
				 long evthrees=n/6l;
				 long ans=(2l*odd);
				 long four=evthrees/2l;
				 long five=evthrees/2l;
				 if(evthrees%2==1)four++;
				 ans=(ans+(4l*four));
				 ans=(ans+(5l*five));
				 long rem=(n-odd-four-five);
				 ans=(ans+(3l*rem));
				 out.println(ans%oo);
			 }
		}
		static void C2() throws IOException{
			 int t=ni();
			 while(t-->0) {
				 long n=nl();
				 long odd=(n/2l);
				 if(n%2==1)odd++;
				// odd%=oo;
				 long ans=(2l*odd)%oo;
				 long cur=n-odd;
				 HashMap<Long,Long>hm=new HashMap<>();
				 hm.put(3l,cur);
				 long num=6l;
				 while(num<=n||num<0) {
					 long cnt=(n/num);
					 long ii=(num/2l) +1;
					 HashMap<Long,Long>tmp=new HashMap<>();
					 for(long x:hm.keySet()) {
						 tmp.put(x,hm.get(x)-cnt);
					 }
					 hm.clear();
					 for(long x:tmp.keySet())hm.put(x, tmp.get(x));
					 hm.put(ii,cnt);
					 num=lcm(num,ii);
				 }
				 for(long x:hm.keySet()) {
					 ans=(ans+1l*x*(Math.max(0,hm.get(x))%oo)%oo)%oo;
				 }
				 out.println(ans%oo);
			 }
		}
	static long lcm(long a,long b) {
		return 1l*a*(b/gcd(a,b));
	}

		static boolean isPrime(long n) {
			if(n==2)return true;
			if(n<2||n%2==0)return false;
			
			for(long i=3L;i*i<n;i+=2l) {
				long rem=(n%i);
				if(rem==0)return false;
			}
			return true;
		}
		static long mm[];
		static long mod=998244353l;
		static void D() throws IOException {
			int t=1;
			while(t-->0) {
				int n=ni();
				Long a[][]=new Long[n][2];
				long sum=0;
				for(int i=0;i<n;i++) {
					a[i][0]=nl();
					a[i][1]=nl();
					sum+=a[i][0];
				}
				Arrays.sort(a,(u,v)->u[1]<v[1]?-1:u[1]>v[1]?1:0);
				long paid=0,cnt=0;
				for(int i=0;i<n&&sum>0;i++) {
					long nd=Math.min(sum, a[i][1]-cnt);
					nd=Math.max(nd, 0);
					paid+=nd*2l;
					sum-=nd;
					long cur=Math.min(a[i][0],sum);
					paid+=cur;
					sum-=cur;
					cnt+=nd+cur;
				}
				out.println(paid);
			}
		}
		private static int bfs(int i, int j,int k) {
			boolean [][]vis=new boolean[dist.length][dist[0].length];
			Queue<int[]>q=new LinkedList<int[]>();
			int mn=Integer.MAX_VALUE;
			q.add(new int[] {i,j,0,0});
			int[]dx=new int[] {-1,1,0,0};
			int[]dy=new int[] {0,0,1,-1};
			while(!q.isEmpty()) {
				int []x=q.poll();
				vis[x[0]][x[1]]=true;
				int c=x[2];
				if(c>k/2)continue;
				if(c>0&&k%c==0&&(k/c)%2==0) {
					mn=Math.min(mn,x[3]*k/c );
				}
				for(int a=0;a<4;a++) {
					int nx=x[0]+dx[a];
					int ny=x[1]+dy[a];
					if(valid(nx,ny)&&!vis[nx][ny]) {
						q.add(new int[] {nx,ny,c+1,x[3]+dist[x[0]][x[1]][a]});
					}
				}
				
			}
			return mn;
		}
		private static boolean valid(int nx, int ny) {
			return nx>=0&&nx<dist.length&&ny>=0&&ny<dist[0].length;
		}
		static long gcd (long a2, long b2) {
		    return b2==0?a2:gcd (b2, a2 % b2);
		}
		
	static int[][]rng,dr;
	static Boolean[][]memo;
	static void E() throws IOException {		
			int n=ni(),m=ni();
			rng=new int[n][5];
			for(int i=0;i<n;i++) {
				rng[i][0]=ni();rng[i][1]=ni();rng[i][2]=ni();
				rng[i][3]=ni();rng[i][4]=ni();
			}
			boolean[]lft=new boolean[n];
			boolean[]rit=new boolean[n];
			lft[n-1]=sats(rng[0][0],new Point(rng[0][1],rng[0][2]));
			rit[n-1]=sats(rng[0][0],new Point(rng[0][3],rng[0][4]));
			int prvl=rng[n-1][0],prvr=rng[n-1][0];
			Point ll=new Point(rng[n-1][1],rng[n-1][2]);
			Point lr=new Point(rng[n-1][3],rng[n-1][4]);
			Point rl=new Point(rng[n-1][1],rng[n-1][2]);
			Point rr=new Point(rng[n-1][3],rng[n-1][4]);
			for(int i=n-2;i>=0;i--) {
				ll=inter(ll,rng[i][1],rng[i][2]);
				rr=inter(rr,rng[i][3],rng[i][4]);
				boolean x=false,y=false;
				if(ll.x!=-1&&sats(rng[i][0],ll)&&sats(prvr,lr)) {
					lft[i]=true;
					//rl=new Point(rng[i][1],rng[i][2]);
					x=true;
					prvl=rng[i][0];
				}
				if(rr.x!=-1&&sats(rng[i][0],rr)&&sats(prvl,rl)) {
					rit[i]=true;
					//lr=new Point(rng[i][3],rng[i][4]);
					y=true;
					prvr=rng[i][0];
				}
				if(x) {
					rl=new Point(rng[i][1],rng[i][2]);
					ll=new Point(rng[i][1],rng[i][2]);
				}
				if(y) {
					lr=new Point(rng[i][3],rng[i][4]);
					rr=new Point(rng[i][3],rng[i][4]);
				}
			}
			//out.println(Arrays.toString(lft));
			//out.println(Arrays.toString(rit));
			int[]closel=new int[n],closer=new int[n];
			int l=n-1,r=n-1;
			for(int i=n-2;i>=0;i--) {
				if(lft[i])l=i;
				if(rit[i])r=i;
				closel[i]=r;closer[i]=l;
			}
			//out.println(Arrays.toString(closel));
			//out.println(Arrays.toString(closer));
			int mn=Math.min(closel[0], closer[0]);
			if(mn==n-1)out.println("NO");
			else {
				ol("YES");
				int[]ans=new int[n];
				int cur=0,idl=0,idr=0;
				for(int i=0;i<n-1;i++) {
					if(rit[i]) {
						ans[i]=1;
						cur=0;
					}else if(lft[i]) {
						cur=1;
					}else ans[i]=cur;
					if(ans[i]==0) {
						idl=rng[i][0];
					}else idr=rng[i][0];
				}
				if(!sats(idr,new Point(rng[n-1][3],rng[n-1][4])))ans[n-1]=1;
				for(int i=0;i<ans.length;i++)out.print(ans[i]+" ");
				ol("");
			}
	}
	private static boolean sats(int i, Point a) {
		return i>=a.x&&i<=a.y;
	}
	private static Point inter(Point ll, int i, int j) {
		int x=Math.max(ll.x, i);
		int y=Math.min(ll.y, j);
		if(x>y)x=y=-1;
		return new Point(x,y);
	}
	private static boolean memo(int i, int prv) {
		if(i==memo.length)return true;
		if(memo[i][prv]!=null)return memo[i][prv];
		boolean ch1=false,ch2=false;
		if(rng[i][0]>=rng[i][1]&&rng[i][0]<=rng[i][2]) {
			ch1=memo(i+1,0);
		}
		if(rng[i][0]>=rng[i][3]&&rng[i][0]<=rng[i][4]) {
			ch2=memo(i+1,1);
		}
		dr[i][prv]=ch1?1:2;
		return memo[i][prv]=ch1||ch2;
	}
	static int[] zalg(String s) {
		int n=s.length();
		int[]z=new int[n];
		for(int i=1,l=0,r=0;i<s.length();i++) {
			if(i<=r) {
				z[i]=Math.min(r-i+1, z[i-l]);
			}
			while(i+z[i]<n&&s.charAt(z[i])==s.charAt(i+z[i]))z[i]+=1;
			if(i+z[i]-1<r) {
				l=i;
				r=i+z[i]-1;
			}
		}
		return z;
	}
	static void F() throws IOException {
		int t=ni();
		while(t-->0) {
			
		}
	}
	static void CC() throws IOException {
		for(int kk=2;kk<21;kk++) {
			ol(kk+"   -------");
		int n=kk;
		int k=n-2;
		int msk=1<<k;
		int[]a=new int[k];
		for(int i=0;i<a.length;i++)a[i]=i+2;
		int mx=1;
		int ms=0;
		for(int i=1;i<msk;i++) {
			long prod=1;
			int cnt=0;
			for(int j=0;j<a.length;j++) {
				if(((i>>j)&1)!=0) {
					prod*=a[j];
					cnt++;
				}
			}
			if(cnt>=mx&&prod%n==1) {
				mx=cnt;
				ms=i;
			}
			
		}
		ol(mx==1?mx:mx+1);
		out.print(1+" ");
		long pr=1;
		for(int j=0;j<a.length;j++) {
			if(((ms>>j)&1)!=0) {
				out.print(a[j]+" ");
				pr*=a[j];
			}
		}
		ol("");
		ol("Prod: "+pr);
		ol(n+"*"+((pr-1)/n)+" + "+1);
		}
	}
	static int ni() throws IOException {
		return sc.nextInt();
	}
	static double nd() throws IOException {
		return sc.nextDouble();
	}
	static long nl() throws IOException {
		return  sc.nextLong();
	}
	static String ns() throws IOException {
		return sc.next();
	}
	static int[] nai(int n) throws IOException {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = sc.nextInt();
		return a;
	}
	static long[] nal(int n) throws IOException {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = sc.nextLong();
		return a;
	}
	static int[][] nmi(int n,int m) throws IOException{
		int[][]a=new int[n][m];
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				a[i][j]=sc.nextInt();
			}
		}
		return a;
	}

	static long[][] nml(int n,int m) throws IOException{
		long[][]a=new long[n][m];
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				a[i][j]=sc.nextLong();
			}
		}
		return a;
	}
	static void o(String x) {
		out.print(x);
	}
	static void ol(String x) {
		out.println(x);
	}
	static void ol(int x) {
		out.println(x);
	}
	static void disp1(int []a) {
		for(int i=0;i<a.length;i++) {
			out.print(a[i]+" ");
		}
		out.println();
	}
	static class Pair implements Comparable<Pair>{
		int x,y;
		Pair(int x,int y){
			this.x=x;this.y=y;
		}
		@Override
		public int compareTo(Pair p) {
			return x-p.x==0?y-p.y:x-p.x;
		}
		
	}
	static class Scanner 
	{
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

		public String next() throws IOException 
		{
			while (st == null || !st.hasMoreTokens()) 
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public boolean hasNext() {return st.hasMoreTokens();}
		public int nextInt() throws IOException {return Integer.parseInt(next());}
		
		public double nextDouble() throws IOException {return Double.parseDouble(next());}
		
		public long nextLong() throws IOException {return Long.parseLong(next());}

		public String nextLine() throws IOException {return br.readLine();}
			
		public boolean ready() throws IOException {return br.ready(); }
		

	}
}