The number "zero" is called "love" (or "l'oeuf" to be precise, literally means "egg" in French), for example when denoting the zero score in a game of tennis. 

Aki is fond of numbers, especially those with trailing zeros. For example, the number 9200 has two trailing zeros. Aki thinks the more trailing zero digits a number has, the prettier it is.

However, Aki believes, that the number of trailing zeros of a number is not static, but depends on the base (radix) it is represented in. Thus, he considers a few scenarios with some numbers and bases. And now, since the numbers he used become quite bizarre, he asks you to help him to calculate the beauty of these numbers.

Given two integers n and b (in decimal notation), your task is to calculate the number of trailing zero digits in the b-ary (in the base/radix of b) representation of n ! ([factorial](https://en.wikipedia.org/wiki/Factorial) of n). 

Input

The only line of the input contains two integers n and b (1 ≤ n ≤ 10^{18}, 2 ≤ b ≤ 10^{12}).

Output

Print an only integer — the number of trailing zero digits in the b-ary representation of n!

Examples

Input

6 9


Output

1


Input

38 11


Output

3


Input

5 2


Output

3


Input

5 10


Output

1

Note

In the first example, 6!_{(10)} = 720_{(10)} = 880_{(9)}.

In the third and fourth example, 5!_{(10)} = 120_{(10)} = 1111000_{(2)}.

The representation of the number x in the b-ary base is d_1, d_2, …, d_k if x = d_1 b^{k - 1} + d_2 b^{k - 2} + … + d_k b^0, where d_i are integers and 0 ≤ d_i ≤ b - 1. For example, the number 720 from the first example is represented as 880_{(9)} since 720 = 8 ⋅ 9^2 + 8 ⋅ 9 + 0 ⋅ 1.

You can read more about bases [here](https://en.wikipedia.org/wiki/Radix).

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;


public class SpecialistC6 {
	static PrintWriter out;
	static Scanner sc;
	private static boolean[] is_composite;
	private static ArrayList<Integer> primes;
	
	public static void main(String[]args) throws IOException {
		sc=new Scanner(System.in);
		out=new PrintWriter(System.out);
		//A();
		//B();
		//C();
		//D();
		//E();
		//F();
		//G();
		//H();
		//I();
		//J();
		//K();
		//L();
		//M();
		//N();
		O();
		//P();
		//Q();
		//R();
		//S();
		//T();
		//U();
		out.close();
	}
	  private static void A() throws IOException {
		    int n;
		    sieve((int)1e6);
		    boolean[]prime=new boolean[(int)1e6 +1];
			for(int x:primes) {
				prime[x]=true;
			}
			while((n=ni())!=0) {
				int mxdiff=-1,a=-1,b=-1;
				for(int x:primes) {
					if(x>n/2)break;
					if(prime[n-x]&&Math.abs(n-2*x)>mxdiff) {
						mxdiff=Math.abs(n-2*x);a=x;b=n-x;
					}
				}
				if(a>b) {a^=b;b^=a;a^=b;}
				out.println(n+" = "+a+" + "+b);
			}
	   }
	
		static void B() throws IOException {
			int t=ni();
			sieve((int)1e6);			
			while(t-->0) {
				int lo=ni(),hi=ni();
				int[]occ=new int[1000];
				int num=0;
				for(int i=1;i<primes.size();i++) {
					if(primes.get(i)>=lo&&primes.get(i)<=hi) {
						if(primes.get(i-1)>=lo&&primes.get(i-1)<=hi) {
							occ[primes.get(i)-primes.get(i-1)]++;
						}
					}
					if(primes.get(i)>hi)break;
				}
				int mx=0;
				for(int i=1;i<occ.length;i++) {
					if(occ[i]>occ[mx]) mx=i;
				}
				int val=occ[mx];boolean can=true;
				for(int i=1;i<occ.length;i++) {
					if(occ[i]==val&&mx!=i) {
						can=false;break;
					}
				}
				if(!can||mx==0) {
					ol("No jumping champion");
				}else {
					ol("The jumping champion is "+mx);
				}
			}
		}
	
		static int gcd (int a, int b) {
		    return b==0?a:gcd (b, a % b);
		}
		static long lcm(int a,int b) {
			return (a / gcd(a,b))*b*1l;
		}
		static boolean prime[];
		static void C() throws IOException{
			int n=ni();
			int[]occ=new int[(int)1e6];
			sieve(occ.length);
			prime=new boolean[occ.length];
			for(int x:primes)prime[x]=true;
			for(int i=2;i<occ.length;i++) {
				occ[i]=occ[i-1];
				if(digPrime(i))occ[i]++;
			}
			while(n-->0) {
				out.println(-occ[ni()-1]+occ[ni()]);
			}
		}
	
		private static boolean digPrime(int i) {
			int sum=0,tmp=i;
			while(i!=0) {
				sum+=i%10;
				i/=10;
			}
			return prime[sum]&&prime[tmp];
		}
		static void D() throws IOException {
			int t=3;
			sieve((int)2e4 );
			int[]occ=new int[(int)1e4 +1];
//			prime=new boolean[occ.length];
//			for(int x:primes)prime[x]=true;
			occ[0]=1;
			for(int i=1;i<occ.length;i++) {
				occ[i]=occ[i-1];
				if(isPrime(i*i + i +41)) {
					occ[i]++;
				}
			}
			while(sc.ready()) {
				int a=ni()-1,b=ni();
				int ans=occ[b]-(a==-1?0:occ[a]);
				out.printf("%.2f",ans*100/(double)(b-a));
				ol("");
			}
		}
		
	private static boolean isPrime(int i) {
			//if(i<=(int)1e6)return prime[(int)i];
			int idx=0,p=primes.get(0);
			while(1l*p*p<=i) {
				if(i%p==0)return false;
				p=primes.get(++idx);
			}
			return true;
		}
	static void E() throws IOException {
		//int n;
		sieve(100);
		prime=new boolean[101];
		for(int x:primes)prime[x]=true;
		ArrayList<BigInteger>ans=new ArrayList<BigInteger>();
		HashSet<BigInteger>hs=new HashSet<BigInteger>();
		BigInteger bg=new BigInteger("18446744073709551615");
		long mx=(1<<16);
		ans.add(new BigInteger(""+1));
		for(long i=2;i<mx;i++) {
			//if(hs.contains(new BigInteger(i+"")))continue;
			for(int j=4;j<=64;j++) {
				if(prime[j])continue;
				BigInteger base=new BigInteger(i+"");
				BigInteger num=base.pow(j);
				if(num.compareTo(bg)>0)break;
				hs.add(num);
			}
		}
		for(BigInteger x:hs)ans.add(x);
		Collections.sort(ans);
		for(BigInteger x:ans)ol(""+x.toString());
		//ol(ans.size());
	}

	
	private static int gt(int M) {
		int ans = 0, idx = 0, p = primes.get(0);
		long N=Math.abs((long)M);
		while(1l*p * p <= N)
		{
			int e = 0;
			while(N % p == 0) { N /= p; ++e; }
			ans = gcd(ans,e);
			//if(idx<primes.size()-1)
			p = primes.get(++idx);
			//else p++;
		}
		if(N != 1)
			ans = 1;
		if(M<0) {
			while(ans%2==0)ans/=2;
		}
		return ans;
	}
	static void sieve(int N)
	{
		primes = new ArrayList<Integer>();
		
		boolean[] isComposite = new boolean[N];
		for(int i = 2; i < N; ++i)
			if(!isComposite[i])
			{
				primes.add(i);
				if(1l*i*i<N) {
				for(int j = i * i; j < N; j += i)
					isComposite[j] = true;
				}
			}
	}
	static int numDiv(int N)
	{
		int ans = 1, idx = 0, p = primes.get(0);
		while(p * p <= N)
		{
			int e = 0;
			while(N % p == 0) { N /= p; ++e; }
			ans *= (e + 1);
			p = primes.get(++idx);
		}
		if(N != 1)
			ans <<= 1;
		return ans;
	}
	
	static void F() throws IOException {
		int tc=1,n;
		long[]ans=new long[(int)1e6 +1];
		sieve((int)1e6 +10);
		//ans[5]=1;
		for(int i=5,ptr1=0,ptr2=1;i<ans.length;i++) {
			//ans[i]=ans[i-1];
			int lo=primes.get(ptr1),hi=primes.get(ptr2);
			if(ptr2<primes.size()-1&&primes.get(ptr2+1)+lo<=i) {
				ptr2++;
			}
			else if(ptr2<primes.size()-1&&primes.get(ptr2+1)+2<=i) {
				ptr2++;ptr1=0;
			}
			else if(ptr1<primes.size()-1&&ptr1<ptr2-1&&primes.get(ptr1+1)+hi<=i) {
				ptr1++;
			}
			//if(ptr2-2>0) {
			ans[i]=(1l*(ptr2-1)*(ptr2))/2l;
			//}
			ans[i]+=ptr1+1;
		}
		while((n=ni())!=0) {
			out.println("Case "+tc+++": "+ans[n]);
		}
		
	}
	static int[] gcdExtended(int p, int q) {
	      if (q == 0)
	         return new int[] { p, 1, 0 };

	      int[] vals = gcdExtended(q, p % q);
	      int d = vals[0];
	      int a = vals[2];
	      int b = vals[1] - (p / q) * vals[2];
	      return new int[] { d, a, b };
	   }
	static ArrayList<Point>prs;
	static void G() throws IOException {
		sieve(40000);
		while(true) {
			String[]s=sc.nextLine().split(" ");
			if(s.length==1)break;
			int num=1;
			for(int i=0;i<s.length;i+=2) {
				num*=powMod(Integer.parseInt(s[i]),
						Integer.parseInt(s[i+1]),100000);
			}
			num--;
			prs=new ArrayList<Point>();
			fact(num);
			Collections.sort(prs,(u,v)->v.x-u.x);
			for(int i=0;i<prs.size();i++) {
				Point p=prs.get(i);
				out.print(p.x+" "+p.y+(i==prs.size()-1?"":" "));	
			}
			ol("");
		}
	}
	
	private static void fact(int n) {
		int idx=0,p=primes.get(0);
		while(1l*p*p<=n) {
			int e=0;
			while(n%p==0) {
				n/=p;e++;
			}
			if(e>0)prs.add(new Point(p,e));
			p=primes.get(++idx);
		}
		if(n!=1)prs.add(new Point(n,1));
		
	}
	static void H() throws IOException {
		int t=3;
		sieve(1<<21);
		while(sc.ready()) {
			int n=ni(),b=ni();
			int[]cnt=new int[1<<21];
			int[]cnt2=new int[1<<21];
			int id=0,p=primes.get(0);
			int tm=b;
			while(p*p<=tm) {
				while(tm%p==0) {
					tm/=p;
					cnt[p]++;
				}
				p=primes.get(++id);
			}if(tm!=1)cnt[tm]++;
			int zeros=Integer.MAX_VALUE;
			double cn=0;
			for(int i=2;i<=n;i++) {
				tm=i;
				id=0;p=primes.get(0);
				while(1l*p*p<=tm) {
					while(tm%p==0) {
						tm/=p;
						cnt2[p]++;
					}
					p=primes.get(++id);
				}if(tm!=1) {
					cnt2[tm]++;
				}
			}
			for(int i=2;i<cnt2.length;i++) {
				if(cnt2[i]>0)
				cn+=cnt2[i]*Math.log10(i);
			}
			if(Math.abs(Math.round(cn)-cn)<1e-6) {
				cn=Math.round(cn);
			}
			cn/=Math.log10(b);
			if(Math.abs(Math.round(cn)-cn)<1e-6) {
				cn=Math.round(cn);
			}
			cn++;
			for(int i=2;i<Math.min(cnt.length,cnt2.length);i++) {
				if(cnt[i]>0)zeros=Math.min(cnt2[i]/cnt[i], zeros);
			}
			out.println(zeros+" "+((int)cn));
		}
	}

	static void I() throws IOException {
		int t=5;
		sieve(1<<17);
		while(sc.ready()) {
			int a=ni(),b=ni();
//			HashMap<Integer,Integer>fac=new HashMap<Integer, Integer>();
//			for(int i=2;i<=a;i++)factor(i,fac);
			HashMap<Long,Integer>fac2=new HashMap<Long, Integer>();
			factor(b,fac2);
			boolean isDiv=true;
			for(long x:fac2.keySet()) {
				int val=fac2.get(x);
				long fctX=sol((long)a,(int)x);
				if(val>fctX) {
					isDiv=false;break;
				}
			}
			if(isDiv) {
				ol(b+" divides "+a+"!");
			}else {
				ol(b+" does not divide "+a+"!");
			}
		}
	}

	private static long sol(long a, long x) {
		if(a==0)return 0l;
		return a/x + sol(a/x,x);
	}
	private static void factor(long a, HashMap<Long, Integer> fac) {
			int idx=0,p=primes.get(0);
			while(1l*p*p<=a) {
				int cnt=0;
				while(a%p==0) {a/=p;
					cnt++;
				}
				if(cnt>0)
					fac.put((long)p, fac.getOrDefault(p, 0)+cnt);
				p=primes.get(++idx);
			}
			if(a!=1)fac.put(a, fac.getOrDefault(a, 0)+1);
	}
	static void J() throws IOException {
		int t=6;
		sieve((int)1e6);
		int[]ans=new int[(int)1e6 +1];
		for(int i=2;i<ans.length;i++) {
			ans[i]=ans[i-1]+fct(i);
		}
		while(sc.ready()) {
			int n=ni();
			ol(ans[n]);
		}
	}

	private static int fct(int n) {
		int idx=0,p=primes.get(0);
		int ans=0;
		while(1l*p*p<=n) {
			while(n%p==0) {
				n/=p;ans++;
			}
			p=primes.get(++idx);
		}
		if(n!=1)ans++;
		return ans;
	}
	static void K() throws IOException {
		sieve(10000);
		int[]ans=new int[2703664];
		for(int i=2;i<ans.length;i++) {
			ans[i]=ans[i-1]+fct(i);
		}
	//	ol(ans[ans.length-1]);
		int tc=1,n;
		while((n=ni())>=0) {
			int idx=Arrays.binarySearch(ans, n);
			if(n==0)idx=0;
			if(idx<0) {
				ol("Case "+tc+++": Not possible.");
			}else {
				ol("Case "+tc+++": "+idx+"!");
			}
		}
	}
	
	static void L() throws IOException {
		int t=ni();
		int[]ans=new int[(int)1e6 +1];
		Arrays.fill(ans, 1);
		ans[0]=0;
		for(int i=2;i<ans.length;i++) {
			for(int j=i;j<ans.length;j+=i) {
				ans[j]++;
			}
		}
		int[]ids=new int[ans.length];
		for(int i=1;i<ans.length;i++) {
			int cur=ids[i-1];
			if(ans[i]>=ans[ids[i-1]])cur=i;
			ids[i]=cur;
		}
		while(t-->0) {
			ol(ids[ni()]);
		}
	}
	static void N() throws IOException {
		int n=ni();
		int[]a=nai(n);
		int[]cnt=new int[3];
		for(int i=0;i<n;i++) {
			int cur=a[i];
			int ans=0;
			while(cur>0) {
				ans+=cur%10;cur/=10;
			}
			a[i]=ans%3;
			cnt[a[i]]++;
		}
		out.println(cnt[0]/2 + Math.min(cnt[1], cnt[2]));
	}
	static void M() throws IOException {
		int s,t;
		while((s=ni())!=0) {
			t=ni();
			
		}
	}
	static void O() throws IOException {
		long n=nl(),b=nl();
		sieve((int)1e6 + 10);
		HashMap<Long, Integer>hm=new HashMap<Long, Integer>();
		factor(b, hm);
		long mn=(long)1e18;
		for(long x:hm.keySet()) {
			long val=sol(n,x);
			mn=Math.min(mn,val/hm.get(x));
		}
		ol(""+mn);
	}
	static int cnt,nn;
	static void P() throws IOException {
		int arr[]=nai(4);
		int a=ni(),b=ni();
		int ans=0;
		for(int l=a;l<=b;l++) {
			cnt=0;
			int[]tmp=arr;
			nn=l;
			permute(tmp);
			if(cnt>=7)ans++;
		}
		ol(ans);
	}
	public static void permute(int[] nums) {
	    helper(0, nums);
	}
	 
	private static void helper(int start, int[] nums){
	    if(start==nums.length-1){
	    	int tmp=nn;
	    	for(int i=0;i<nums.length;i++)tmp%=nums[i];
	    	if(nn==tmp)cnt++;
	        return;
	    }
	 
	    for(int i=start; i<nums.length; i++){
	        swap(nums, i, start);
	        helper(start+1, nums);
	        swap(nums, i, start);
	    }
	}
	 
	private static void swap(int[] nums, int i, int j){
	    int temp = nums[i];
	    nums[i] = nums[j];
	    nums[j] = temp;
	}
	static void Q() throws IOException {
		int n=ni();
		long h=nl(),k=nl();
		long[]a=nal(n);
		long ans=0;
		long sum=0;
		for(int i=0;i<n;i++) {
			if(sum+a[i]>h) {
				long needed=h-a[i];
				long num=(int)Math.ceil((sum-needed)/(double)k);
				ans+=num;
				sum-=num*1l*k;
				sum=Math.max(sum, 0l);
			}
			sum+=a[i];
			
		}
		ans+=(int)Math.ceil(sum/(double)k);
		//ans+=Math.ceil(sum/(double)k);
		ol(""+ans);
	}
	static int modPowLoop(long b, int e, int mod)
	{
		long res = 1;
		while(e > 0)
		{
			if((e & 1) == 1)
				res = res * b % mod;
			b = b * b % mod;
			e >>= 1;
		}
		return (int)res;
	}
	static void R() throws IOException {
		HashSet<Integer>hh=new HashSet<Integer>();
		HashMap<Integer, Boolean>hs=new HashMap<Integer, Boolean>();
		hh.add(561);
		hh.add(1105);
		hh.add(1729);
		hh.add(2465);
		hh.add(2821);
		hh.add(6601);
		hh.add(8911);
		hh.add(10585);
		hh.add(15841);
		hh.add(41041);
		hh.add(46657);
		hh.add(29341);
		hh.add(52633);
		hh.add(62745);
		hh.add(63973);
		int n;
		StringBuilder sb=new StringBuilder();
//		while((n=ni())!=0) {
//			if(hh.contains(n)) {
//				ol("The number "+n+" is a Carmichael number.");
//			}else {
//				ol(n+" is normal.");
//			}
//		}
		while((n=ni())!=0) {
			boolean prime=true,all=true;
			if(n%2==0)all=false;
			for(int i=2;i<n&&all;i++) {
				if(n%i==0)prime=false;
				int pow=(int) modPowLoop(i,n,n);
				if(pow!=i)all=false;
			}
			if(!prime&&all) {
				ol("The number "+n+" is a Carmichael number.");
			}
				else {
				ol(n+" is normal.");
			}
		}
		//out.print(sb);
	}
	private static long powMod(long a, long n, int mod) {
		if(n==0)return 1l;
		long sq=powMod(a, n/2, mod)%mod;
		sq=(1l*sq*sq)%mod;
		if(n%2==1)sq=(1l*sq*a)%mod;		
		return (int)sq;
	}
	private static long powMod2(long a, long n, int mod) {
		if(n==0)return 1l;
		long sq=powMod(a, n/2, mod);
		while(sq%10==0&&sq>=10)sq/=10;
		sq%=10;
		sq*=sq;
		while(sq%10==0&&sq>=10)sq/=10;
		sq%=10;
		if(n%2==1) {
			sq=sq*a;		
			while(sq%10==0&&sq>=10)sq/=10;
			sq%=10;
		}
		return (int)sq;
	}
	
static void S() throws IOException {
		int n;
		while((n=ni())!=0) {
			long kk=ni()-1,mm=ni()-1;
			int k=(int)(kk%n),m=(int)(mm%n);
			ArrayList<Integer>arr=new ArrayList<Integer>();
			int idx1=0,idx2=n-1;//n1 goes right,n2 goes left
			for(int i=0;i<n;i++)arr.add(i+1);
			ArrayList<Point>ans=new ArrayList<Point>();
			while(arr.size()>1) {
				int id1_new=(idx1+k)%arr.size();
				int id2_new=(idx2-m+arr.size())%arr.size();
				while(id2_new<0)id2_new+=arr.size();
				int nxt1=(id1_new+1)%arr.size();
				if(nxt1==id2_new) {
					nxt1=(nxt1+1)%arr.size();
				}
				int nxt2=(id2_new-1+arr.size())%arr.size();
				if(nxt2==id1_new) {
					nxt2=(nxt2-1+arr.size())%arr.size();
				}
				nxt1=arr.get(nxt1);nxt2=arr.get(nxt2);
				int e1=arr.get(id1_new);
				int e2=arr.get(id2_new);
				arr.remove(new Integer(e1));
				if(e1!=e2)arr.remove(new Integer(e2));
				for(int i=0;i<arr.size();i++) {
					if(arr.get(i)==nxt1) {
						idx1=i;
					}
					if(arr.get(i)==nxt2) {
						idx2=i;
					}
				}
				ans.add(new Point(e1,e2));	
			}
			if(arr.size()==1)ans.add(new Point(arr.get(0),arr.get(0)));
			StringBuilder sb=new StringBuilder();
			for(Point p:ans) {
				int x=p.x,y=p.y;
				sb.append(" ");
				if(x<10) {
					sb.append(" ");
				}
				sb.append(x);
				if(y!=x) {
					sb.append(" ");
					if(y<10) {
						sb.append(" ");
					}
					sb.append(y);
				}
				sb.append(",");
			}
			String s=sb.toString();
			ol(s.substring(0,s.length()-1));
		}
		//ni();ni();
	}	
static void T() throws IOException {
		int n;
		sieve(400);
		long[]tbl=new long[50001];
		tbl[1]=1l;
		for(int i=2;i<tbl.length;i++) {
			tbl[i]=tbl[i-1]+phi(i);
		}
		//for(int i=1;i<=10000;i++)ol(""+tbl[i]);
		while((n=ni())!=0) {
			ol(""+(2*tbl[n]-1));
		}
	}
	private static int phi(int n) {//euler totient
		int p=primes.get(0),idx=0,ans=n;
		while(1l*p*p<=n) {
			if(n%p==0) {
				if(ans%p==0)
					ans-=ans/p;
				while(n%p==0)n/=p;
				
			}
			p=primes.get(++idx);
		}
		if(n!=1)ans-=ans/n;
	return ans;
}

	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;
		}
		public boolean equals(Object o) {
	        if (this == o) return true;
	        if (!(o instanceof Pair)) return false;
	        Pair key = (Pair) o;
	        return x == key.x && y == key.y;
	    }

	    @Override
	    public int hashCode() {
	        int result = x;
	        result = 31 * result + y;
	        return result;
	    }
	}
	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(); }
		

	}
}
