You are given an array a of n integers, and another integer k such that 2k ≤ n.

You have to perform exactly k operations with this array. In one operation, you have to choose two elements of the array (let them be a_i and a_j; they can be equal or different, but their positions in the array must not be the same), remove them from the array, and add ⌊ (a_i)/(a_j) ⌋ to your score, where ⌊ x/y ⌋ is the maximum integer not exceeding x/y.

Initially, your score is 0. After you perform exactly k operations, you add all the remaining elements of the array to the score.

Calculate the minimum possible score you can get.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 500) — the number of test cases.

Each test case consists of two lines. The first line contains two integers n and k (1 ≤ n ≤ 100; 0 ≤ k ≤ ⌊ n/2 ⌋).

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 2 ⋅ 10^5).

Output

Print one integer — the minimum possible score you can get.

Example

Input


5
7 3
1 1 1 2 1 3 1
5 1
5 5 5 5 5
4 2
1 3 3 7
2 0
4 2
9 2
1 10 10 1 10 2 7 10 3


Output


2
16
0
6
16

Note

Let's consider the example test.

In the first test case, one way to obtain a score of 2 is the following one:

  1. choose a_7 = 1 and a_4 = 2 for the operation; the score becomes 0 + ⌊ 1/2 ⌋ = 0, the array becomes [1, 1, 1, 1, 3]; 
  2. choose a_1 = 1 and a_5 = 3 for the operation; the score becomes 0 + ⌊ 1/3 ⌋ = 0, the array becomes [1, 1, 1]; 
  3. choose a_1 = 1 and a_2 = 1 for the operation; the score becomes 0 + ⌊ 1/1 ⌋ = 1, the array becomes [1]; 
  4. add the remaining element 1 to the score, so the resulting score is 2. 



In the second test case, no matter which operations you choose, the resulting score is 16.

In the third test case, one way to obtain a score of 0 is the following one:

  1. choose a_1 = 1 and a_2 = 3 for the operation; the score becomes 0 + ⌊ 1/3 ⌋ = 0, the array becomes [3, 7]; 
  2. choose a_1 = 3 and a_2 = 7 for the operation; the score becomes 0 + ⌊ 3/7 ⌋ = 0, the array becomes empty; 
  3. the array is empty, so the score doesn't change anymore. 



In the fourth test case, no operations can be performed, so the score is the sum of the elements of the array: 4 + 2 = 6.
1
6 3
4 4 5 5 6 6
 1
6 3
1 1 1 1 2 2
 1
9 3
1 1 1 2 2 2 3 3 3
 1
10 5
3 3 3 4 4 4 5 5 5 1
 1
10 4
1 1 1 2 3 3 3 3 4 5
 1
77 9
9 8 10 5 8 20 17 19 14 16 7 6 15 16 6 13 10 13 14 12 5 6 12 14 12 8 13 12 17 8 12 17 2 11 8 18 17 2 13 2 1 19 9 8 10 20 8 12 15 1 3 15 6 19 4 11 12 8 3 2 1 20 15 14 6 10 11 1 5 11 10 6 20 6 14 16 6
 1
14 7
1 1 1 1 1 1 1 2 2 2 2 2 3 3
 1
88 38
9 143 135 72 74 12 120 27 108 183 18 24 163 122 140 155 166 188 197 14 134 66 188 161 79 100 40 55 161 118 121 18 72 141 136 31 39 187 2 98 16 118 120 196 127 66 135 186 49 16 17 50 107 192 50 23 62 110 83 124 197 127 185 129 131 182 45 147 174 115 89 109 177 7 70 43 75 5 157 93 59 26 176 105 32 89 65 6
 5
7 3
1 1 1 2 1 3 1
5 1
5 5 5 5 5
4 2
1 3 3 7
2 0
4 2
10 5
3 3 3 4 4 4 5 5 5 1
 1
87 12
10 5 11 7 16 16 8 11 14 11 4 4 3 7 16 12 2 3 3 13 1 7 11 16 4 7 11 5 3 15 20 5 12 1 8 8 13 19 3 7 14 3 4 10 18 13 20 1 4 8 10 12 4 7 15 2 18 13 6 2 1 2 10 13 4 5 18 7 1 10 6 2 19 17 5 11 10 12 14 6 16 20 11 12 10 3 6
 1
16 8
1 1 2 2 3 3 3 3 3 3 3 3 3 4 5 5
 1
8 4
1 1 3 3 3 3 5 6
 1
12 6
1 1 1 8 8 8 8 8 8 10 10 10
 5
7 3
1 1 1 2 1 3 1
5 1
5 5 5 5 5
4 2
1 3 3 7
6 3
2 2 3 3 4 4
9 2
1 10 10 1 10 2 7 10 3
 1
12 6
1 1 1 1 1 2 2 2 2 3 3 3
 1
100 34
2 6 5 4 4 4 5 7 6 6 1 2 5 1 4 4 4 5 5 5 2 3 5 6 6 1 1 3 7 5 4 4 1 3 4 6 4 2 7 6 5 4 6 1 1 2 4 6 4 2 2 6 6 3 5 3 4 5 3 4 3 2 1 7 7 5 4 6 3 1 6 7 6 2 2 2 4 7 3 2 6 1 1 3 1 5 6 4 4 7 2 6 6 5 4 4 3 5 2 4
 1
85 3
43 17 34 67 14 7 80 48 36 95 48 68 86 4 17 46 51 87 41 90 100 56 57 42 9 8 27 23 16 14 99 22 13 98 89 24 77 59 15 94 25 81 4 71 24 43 97 88 97 10 6 8 3 86 28 61 100 98 76 85 32 18 79 66 51 44 28 99 87 56 80 93 89 76 7 57 96 39 46 25 4 67 6 51 39
 1
6 3
1 1 2 2 3 3
 1
6 3
2 3 3 3 4 4
 1
6 3
1 7 7 7 10 10
 1
10 3
1 7 4 3 2 2 6 7 4 7
 1
100 17
5 1 1 7 3 2 5 1 1 3 4 5 5 5 7 5 7 5 1 7 6 6 1 3 6 3 4 5 4 6 3 1 7 6 2 3 2 5 3 3 6 5 5 6 5 7 5 3 5 4 7 3 5 1 7 3 4 4 3 3 3 5 1 1 1 7 1 3 2 3 2 7 2 1 6 5 6 6 1 5 4 6 1 7 6 7 6 1 1 1 5 3 5 7 4 6 4 6 3 2
 1
7 3
1 1 1 2 2 3 3
 1
9 2
1 10 10 1 10 2 7 10 191919
 1
6 3
6 6 5 5 1 1
 1
8 3
1 1 6 6 6 6 2 2
 1
91 9
4 3 19 8 3 6 16 5 17 11 9 13 15 8 1 3 20 2 19 7 14 1 6 4 8 18 13 8 16 11 3 12 3 3 12 17 15 9 5 15 12 11 7 20 19 3 4 14 10 9 7 16 12 10 3 6 15 17 4 8 15 2 10 13 11 15 7 20 1 10 9 2 10 15 7 1 6 16 2 1 17 10 19 10 7 18 3 5 10 12 15
 1
67 22
83 41 94 76 47 33 20 51 98 48 92 72 24 51 15 17 35 70 83 95 79 65 80 17 72 7 97 14 74 98 55 63 45 79 42 92 85 24 84 30 29 77 64 68 68 71 89 18 82 68 20 91 84 52 45 23 65 95 83 84 18 81 63 11 89 41 69
 1
4 2
5 6 5 5
 1
6 3
3 3 4 4 7 7
 10
7 3
2 2 2 2 3 3 3
7 3
2 2 3 3 3 4 4
7 3
2 2 2 2 2 2 2
7 3
2 2 3 3 3 4 4
7 3
2 2 2 3 3 3 3
7 3
2 2 3 3 3 3 4
7 3
2 2 2 2 2 3 3
7 3
2 2 3 3 3 3 3
7 3
2 2 2 2 2 2 3
7 3
2 2 2 3 3 3 4
 1
7 3
2 2 2 2 7 8 2
 1
13 6
1 2 2 2 2 3 3 3 3 4 4 4 4
 1
10 3
1 1 1 1 1 1 2 2 3 3
 1
10 3
2 15 14 13 12 15 18 2 9 15
 1
8 4
1 2 2 2 2 3 3 3

0
 1
 3
 0
 2
 489
 0
 140
 2
16
0
6
0
 401
 1
 0
 0
 2
16
0
0
16
 0
 58
 3753
 0
 0
 0
 8
 192
 1
 22
 0
 3
 569
 616
 1
 0
 2
2
5
2
3
3
3
4
4
2
 3
 1
 4
 25
 0

import java.io.*;
import java.util.*;


import java.math.*;
import java.math.BigInteger;


public final class A
{    
	static PrintWriter out = new PrintWriter(System.out); 
	static StringBuilder ans=new StringBuilder();
	static FastReader in=new FastReader();
	static ArrayList<Integer> g[];
	static long mod=(long)998244353,INF=Long.MAX_VALUE;
	//	static boolean set[]; 
	static int par[],partial[];
	static int Days[],P[][];
	static int sum=0,size[];
	static int seg[],col[];
	//	static ArrayList<Long> A;
	static char X[][];
	static boolean set[][];
	static int D[],min[],A[];
	static long dp[][];
	//	static HashSet<Integer> visited,imposters;
	//	static HashSet<Integer> set;
	//	static node1 seg[];
	//static pair moves[]= {new pair(-1,0),new pair(1,0), new pair(0,-1), new pair(0,1)};
	public static void main(String args[])throws IOException
	{	
		/*
		 * star,rope,
		 * BS,LST
		 */		

		int T=i();
		outer:while(T-->0)
		{
			int N=i(),K=i();
		    int A[]=input(N);
		    sort(A);
		    int max=0;
		    HashMap<Integer,Integer> mp=new HashMap<>();
		    for(int i=N-1; i>=(N-2*K); i--)
		    {
		    	int f=mp.getOrDefault(A[i], 0)+1;
		    	mp.put(A[i], f);
		    	max=Math.max(max, f);
		    }
		    long s=0;
		    if(max>K)
		    {
		    	max-=K;
		    	s+=max;
		    }
		    for(int i=0; i<(N-2*K); i++)s+=A[i];
		    
		    ans.append(s+"\n");
		}
		out.println(ans);
		out.close();
	}
	
	static boolean can_loose(Trie root,boolean t)
	{
		if(root==null)return true; //never hits
		int cnt=0;
		for(Trie x:root.A)
		{
			if(x!=null)
			{
				cnt++;
				if(!can_loose(x,t^true)) 
				{
					//System.out.println("TRUE FOR--> "+x.ch+" "+t);
					return true;
				}
			}
		}
		if(cnt==0)return true;
		return false;
	}
	static boolean f(Trie root)
	{
		if(root==null)return false;		
//		int cnt=0;
		for(Trie x:root.A)
		{
			if(x!=null)
			{
//				cnt++;
				if(!f(x))
				{
					
					return true;
				}
			}
		}	
		return false;
	}
	static void insert(String X,Trie head)
	{
		Trie root=head;
        for(char x:X.toCharArray())
        {
        	int a=x-'a';
        	if(root.A[a]==null)root.A[a]=new Trie();
        	root=root.A[a];
        	root.ch=x;
        }
        root.ends=true;        
	}
	static boolean search(String X,Trie head)
	{
		Trie root=head;
		for(char x:X.toCharArray()) {
			int a=x-'a';
			if(root.A[a]==null)return false;
			root=root.A[a];
		}
		return root.ends;
				
	}
	static boolean starts_with(String X,Trie head)
	{
		Trie root=head;
		for(char x:X.toCharArray()) {
			int a=x-'a';
			if(root.A[a]==null)return false;
			root=root.A[a];
		}
		return true;
	}
	static int lower(ArrayList<Integer>A,int i)
	{
		int l=-1,r=A.size();
		while(r-l>1)
		{
			int m=(l+r)/2;
			if(A.get(m)>i)r=m;
			else l=m;
		}		
		return r;
	}
	static int upper(ArrayList<Integer>A,int i)
	{
		int l=-1,r=A.size();
		while(r-l>1)
		{
			int m=(l+r)/2;
			if(A.get(m)<i)l=m;
			else l=m;
		}		
		return l;
	}
	static String f()
	{
		StringBuilder X=new StringBuilder(i()+"");int p=i();
		while(p-->0)X.append("0");
		return X.toString();
	}
	static long f(int i,int g,int x,int left)
	{
		if(x<=1)return left;
		if(i<0 || g==1)return left;
		//		System.out.println(i+" "+g);
		if(dp[i][g]==0)
		{
			int next=min[i];
			int new_gcd=(int)GCD(g,x);
			//System.out.println(" factor--> "+x+" gcd--> "+g+" new-->  "+new_gcd);
			long s=0;
			int c=0;
			for(int j=next+1; j<=i; j++)
			{
				if(A[i]%new_gcd==0)
				{
					s+=new_gcd;
					c--;
				}
			}
			long a=0,b=0;
			a=f(i,g,x-1,left);
			b=s+f(next,new_gcd,x-1,left-c);
			dp[i][g]=Math.max(a, b);
		}
		return dp[i][g];
	}
	static boolean f(int A[],int B[],int x)
	{
		int c=0;
		int N=A.length;
		int l=0,r=x-1;
		for(int i=0; i<N; i++)
		{
			if(A[i]>=r && B[i]>=l)
			{
				r--;
				l++;
				c++;				
			}
			if(c>=x)return true;
		}
		return false;
	}
	static boolean isPalindrome(int A[])
	{
		int i=0,j=A.length-1;
		while(i<j)
		{
			if(A[i]!=A[j])return false;
			i++;
			j--;
		}
		return true;
	}
	static boolean isPalindrome(int A[],int x)
	{
		int i=0,j=A.length-1;
		while(i<j)
		{
			if(A[i]!=A[j])
			{
				if(A[i]==x)i++;
				else if(A[j]==x)j--;
				else return false;
			}
			else
			{
				i++;
				j--;
			}
		}
		return true;
	}
	static long fact[];
	static double nCr(int a,int b)
	{
		double x=fact[a], y=fact[b]*fact[a-b];
		return x/y;
	}
	static int f(ArrayList<Integer> A,int x)
	{
		int l=-1,r=A.size();
		while(r-l>1)
		{
			int m=(l+r)/2;
			if(A.get(m)<x)l=m;
			else r=m;
		}
		return r;
	}
	static boolean f(long a,long b,long x)
	{
		if(b==0)
		{
			return (x==a || x==b);
		}
		if(a<x)return false;
		else
		{
			if(a%b==x%b)return true;
			return f(b,a%b,x);
		}
	}

	static void dfs(int n,int p)
	{
		if(p!=-1)D[n]=D[p]+1;
		for(int c:g[n])
		{
			if(c!=p)
				dfs(c,n);
		}
	}
	static long f(long a,long A[])
	{
		int l=-1,r=A.length;
		while(r-l>1)
		{
			int m=(l+r)/2;
			if(A[m]<=a)l=m;
			else r=m;
		}
		return A[l];
	}
	static void build(int v,int tl,int tr,int A[])
	{
		if(tl==tr)
		{
			seg[v]=A[tl];
			return;
		}
		int tm=(tl+tr)/2;
		build(v*2,tl,tm,A);
		build(v*2+1,tm+1,tr,A);
		seg[v]=Math.min(seg[v*2], seg[v*2+1]);
	}
	static void update(int v,int tl,int tr,int index,int x)
	{
		if(tl==tr && tl==index)
		{
			seg[v]=x;
			return;
		}		
		int tm=(tl+tr)/2;
		if(index<=tm)update(v*2,tl,tm,index,x);
		else update(v*2+1,tm+1,tr,index,x);
		seg[v]=Math.min(seg[v*2], seg[v*2+1]);
	}
	static int ask(int v,int tl,int tr,int l,int r)
	{
		//		System.out.println(v);
		//		if(v>100)return 0;
		if(l>r)return Integer.MAX_VALUE;
		if(tl==l && tr==r)return seg[v];
		int tm=(tl+tr)/2;
		int a=ask(v*2,tl,tm,l,Math.min(tm, r));
		//		System.out.println("for--> "+(v)+" tm--> "+(tm+1)+" tr--> "+tr+" l--> "+Math.max(l, tm+1)+" r--> "+r);
		int b=ask(v*2+1,tm+1,tr,Math.max(l, tm+1),r);
		return Math.min(a, b);
	}
	static int find(int a)
	{
		if(par[a]<0)return a;
		return par[a]=find(par[a]);
	}
	static void union(int a,int b)
	{
		a=find(a);
		b=find(b);
		if(a!=b)
		{
			par[a]+=par[b];
			par[b]=a;
		}
	}
	static int ask(int a,int b)
	{
		System.out.println("? "+a+" "+b);
		return i();
	}




	static long and(int i,int j)
	{
		System.out.println("and "+i+" "+j);
		return l();
	}
	static long or(int i,int j)
	{
		System.out.println("or "+i+" "+j);
		return l();
	}
	static boolean is_Sorted(int A[])
	{
		int N=A.length;
		for(int i=1; i<=N; i++)if(A[i-1]!=i)return false;
		return true;
	}
	static boolean f(StringBuilder sb,String Y,String order)
	{
		StringBuilder res=new StringBuilder(sb.toString());
		HashSet<Character> set=new HashSet<>();
		for(char ch:order.toCharArray())
		{
			set.add(ch);
			for(int i=0; i<sb.length(); i++)
			{
				char x=sb.charAt(i);
				if(set.contains(x))continue;
				res.append(x);
			}
		}

		String str=res.toString();
		return str.equals(Y);
	}
	static boolean all_Zero(int f[])
	{
		for(int a:f)if(a!=0)return false;
		return true;
	}
	static long form(int a,int l)
	{
		long x=0;
		while(l-->0)
		{
			x*=10;
			x+=a;
		}
		return x;
	}
	static int count(String X)
	{
		HashSet<Integer> set=new HashSet<>();
		for(char x:X.toCharArray())set.add(x-'0');
		return set.size();
	}


	//	static void build(int v,int tl,int tr,long A[])
	//	{
	//		if(tl==tr)
	//		{
	//			seg[v]=A[tl];
	//		}
	//		else
	//		{
	//			int tm=(tl+tr)/2;
	//			build(v*2,tl,tm,A);
	//			build(v*2+1,tm+1,tr,A);
	//			seg[v]=Math.min(seg[v*2], seg[v*2+1]);
	//		}
	//	}

	static int [] sub(int A[],int B[])
	{
		int N=A.length;
		int f[]=new int[N];
		for(int i=N-1; i>=0; i--)
		{
			if(B[i]<A[i])
			{
				B[i]+=26;
				B[i-1]-=1;
			}
			f[i]=B[i]-A[i];
		}
		for(int i=0; i<N; i++)
		{
			if(f[i]%2!=0)f[i+1]+=26;
			f[i]/=2;
		}
		return f;
	}





	static int max(int a ,int b,int c,int d)
	{
		a=Math.max(a, b);
		c=Math.max(c,d);
		return Math.max(a, c);
	}
	static int min(int a ,int b,int c,int d)
	{
		a=Math.min(a, b);
		c=Math.min(c,d);
		return Math.min(a, c);
	}



	static HashMap<Integer,Integer> Hash(int A[])
	{
		HashMap<Integer,Integer> mp=new HashMap<>();
		for(int a:A)
		{
			int f=mp.getOrDefault(a,0)+1;
			mp.put(a, f);
		}
		return mp;
	}
	static long mul(long a, long b)
	{
		return ( a %mod * 1L * b%mod )%mod;
	}
	static void swap(int A[],int a,int b)
	{
		int t=A[a];
		A[a]=A[b];
		A[b]=t;
	}



	static boolean isSorted(int A[])
	{
		for(int i=1; i<A.length; i++)
		{
			if(A[i]<A[i-1])return false;
		}
		return true;
	}

	static boolean isDivisible(StringBuilder X,int i,long num)
	{
		long r=0;
		for(; i<X.length(); i++)
		{
			r=r*10+(X.charAt(i)-'0');
			r=r%num;
		}
		return r==0;
	}    



	static int lower_Bound(int A[],int low,int high, int x) 
	{ 
		if (low > high) 
			if (x >= A[high]) 
				return A[high]; 

		int mid = (low + high) / 2; 

		if (A[mid] == x) 
			return A[mid]; 

		if (mid > 0 && A[mid - 1] <= x && x < A[mid]) 
			return A[mid - 1]; 

		if (x < A[mid]) 
			return lower_Bound( A, low, mid - 1, x); 

		return lower_Bound(A, mid + 1, high, x); 
	} 

	static String f(String A)
	{
		String X="";
		for(int i=A.length()-1; i>=0; i--)
		{
			int c=A.charAt(i)-'0';
			X+=(c+1)%2;
		}
		return X;
	}

	static void sort(long[] a) //check for long
	{
		ArrayList<Long> l=new ArrayList<>();
		for (long i:a) l.add(i);
		Collections.sort(l);
		for (int i=0; i<a.length; i++) a[i]=l.get(i);
	}

	static String swap(String X,int i,int j)
	{
		char ch[]=X.toCharArray();
		char a=ch[i];
		ch[i]=ch[j];
		ch[j]=a;
		return new String(ch);
	}

	static int sD(long n)  
	{  

		if (n % 2 == 0 )  
			return 2;  

		for (int i = 3; i * i <= n; i += 2) {  
			if (n % i == 0 )  
				return i;  
		}  

		return (int)n;  
	}  

	static void setGraph(int N)
	{
		//		tot=new int[N+1];
		partial=new int[N+1];
		Days=new int[N+1];
		P=new int[N+1][(int)(Math.log(N)+10)];
		//		set=new boolean[N+1];
		g=new ArrayList[N+1];
		D=new int[N+1];
		for(int i=0; i<=N; i++)
		{

			g[i]=new ArrayList<>();		
			Days[i]=-1;
			D[i]=Integer.MAX_VALUE;
			//D2[i]=INF;
		}
	}



	static  long pow(long a,long b)
	{
		long pow=1;
		long x=a;
		while(b!=0)
		{
			if((b&1)!=0)pow=(pow*x)%mod;
			x=(x*x)%mod;
			b/=2;
		}
		return pow;
	}

	static long toggleBits(long x)//one's complement || Toggle bits
	{
		int n=(int)(Math.floor(Math.log(x)/Math.log(2)))+1;

		return ((1<<n)-1)^x;
	}

	static int countBits(long a)
	{
		return (int)(Math.log(a)/Math.log(2)+1);
	}

	static long fact(long N)
	{ 
		long n=2; 
		if(N<=1)return 1;
		else
		{
			for(int i=3; i<=N; i++)n=(n*i)%mod;
		}
		return n;
	}

	static int kadane(int A[])
	{
		int lsum=A[0],gsum=A[0];
		for(int i=1; i<A.length; i++)
		{
			lsum=Math.max(lsum+A[i],A[i]);
			gsum=Math.max(gsum,lsum);
		}
		return gsum;
	}

	static void sort(int[] a) {
		ArrayList<Integer> l=new ArrayList<>();
		for (int i:a) l.add(i);
		Collections.sort(l);
		for (int i=0; i<a.length; i++) a[i]=l.get(i);
	}

	static boolean isPrime(long N)
	{
		if (N<=1)  return false; 
		if (N<=3)  return true; 
		if (N%2 == 0 || N%3 == 0) return false; 
		for (int i=5; i*i<=N; i=i+6) 
			if (N%i == 0 || N%(i+2) == 0) 
				return false; 
		return true; 
	}
	static void print(char A[])
	{
		for(char c:A)System.out.print(c+" ");
		System.out.println();
	}
	static void print(boolean A[])
	{
		for(boolean c:A)System.out.print(c+" ");
		System.out.println();
	}
	static void print(int A[])
	{
		for(int a:A)System.out.print(a+" ");
		System.out.println();	
	}
	static void print(long A[])
	{
		for(long i:A)System.out.print(i+ " ");
		System.out.println();

	}
	static void print(boolean A[][])
	{
		for(boolean a[]:A)print(a);
	}
	static void print(long A[][])
	{
		for(long a[]:A)print(a);
	}
	static void print(int A[][])
	{
		for(int a[]:A)print(a);
	}
	static void print(ArrayList<Integer> A)
	{
		for(int a:A)System.out.print(a+" ");
		System.out.println();
	}

	static int i()
	{
		return in.nextInt();
	}

	static long l()
	{
		return in.nextLong();
	}

	static int[] input(int N){
		int A[]=new int[N];
		for(int i=0; i<N; i++)
		{
			A[i]=in.nextInt();
		}
		return A;
	}

	static long[] inputLong(int N)     {
		long A[]=new long[N];
		for(int i=0; i<A.length; i++)A[i]=in.nextLong();
		return A;
	}

	static long GCD(long a,long b) 
	{
		if(b==0)
		{
			return a;
		}
		else return GCD(b,a%b);
	}

}
class Trie
{
	char ch;
	Trie A[];
	boolean ends;
	Trie()
	{
		ch='*';
		A=new Trie[26];
		ends=false;
	}
}
class pair1 implements Comparable<pair1>
{
	int a, index;
	pair1(int b,int i)
	{
		a=b;
		index=i;
	}
	public int compareTo(pair1 x)
	{
		return x.a-this.a;
	}
}

//Code For FastReader
//Code For FastReader
//Code For FastReader
//Code For FastReader
class FastReader
{
	BufferedReader br;
	StringTokenizer st;
	public FastReader()
	{
		br=new BufferedReader(new InputStreamReader(System.in));
	}

	String next()
	{
		while(st==null || !st.hasMoreElements())
		{
			try
			{
				st=new StringTokenizer(br.readLine());
			}
			catch(IOException e)
			{
				e.printStackTrace();
			}
		}
		return st.nextToken();
	}

	int nextInt()
	{
		return Integer.parseInt(next());
	}

	long nextLong()
	{
		return Long.parseLong(next());
	}

	double nextDouble()
	{
		return Double.parseDouble(next());
	}

	String nextLine()
	{
		String str="";
		try
		{
			str=br.readLine();
		}
		catch (IOException e)
		{
			e.printStackTrace();
		}
		return str;
	}

}