Gaurang has grown up in a mystical universe. He is faced by n consecutive 2D planes. He shoots a particle of decay age k at the planes.

A particle can pass through a plane directly, however, every plane produces an identical copy of the particle going in the opposite direction with a decay age k-1. If a particle has decay age equal to 1, it will NOT produce a copy.

For example, if there are two planes and a particle is shot with decay age 3 (towards the right), the process is as follows: (here, D(x) refers to a single particle with decay age x) 

  1. the first plane produces a D(2) to the left and lets D(3) continue on to the right; 
  2. the second plane produces a D(2) to the left and lets D(3) continue on to the right; 
  3. the first plane lets D(2) continue on to the left and produces a D(1) to the right; 
  4. the second plane lets D(1) continue on to the right (D(1) cannot produce any copies). 



In total, the final multiset S of particles is \\{D(3), D(2), D(2), D(1)\}. (See notes for visual explanation of this test case.)

Gaurang is unable to cope up with the complexity of this situation when the number of planes is too large. Help Gaurang find the size of the multiset S, given n and k.

Since the size of the multiset can be very large, you have to output it modulo 10^9+7.

Note: Particles can go back and forth between the planes without colliding with each other.

Input

The first line of the input contains the number of test cases t (1 ≤ t ≤ 100). Then, t lines follow, each containing two integers n and k (1 ≤ n, k ≤ 1000). 

Additionally, the sum of n over all test cases will not exceed 1000, and the sum of k over all test cases will not exceed 1000. All test cases in one test are different.

Output

Output t integers. The i-th of them should be equal to the answer to the i-th test case.

Examples

Input


4
2 3
2 2
3 1
1 3


Output


4
3
1
2


Input


3
1 1
1 500
500 250


Output


1
2
257950823

Note

Let us explain the first example with four test cases. 

Test case 1: (n = 2, k = 3) is already explained in the problem statement.

See the below figure of this simulation. Each straight line with a different color represents the path of a different particle. As you can see, there are four distinct particles in the multiset. Note that the vertical spacing between reflected particles is for visual clarity only (as mentioned before, no two distinct particles collide with each other)

<image>

Test case 2: (n = 2, k = 2) is explained as follows:

  1. the first plane produces a D(1) to the left and lets D(2) continue on to the right; 
  2. the second plane produces a D(1) to the left and lets D(2) continue on to the right; 
  3. the first plane lets D(1) continue on to the left (D(1) cannot produce any copies).



Total size of multiset obtained \\{D(1), D(1), D(2)\} is equal to three.

Test case 3: (n = 3, k = 1), there are three planes, but decay age is only one. So no new copies are produced while the one particle passes through the planes. Hence, the answer is one.

Test case 4: (n = 1, k = 3) there is only one plane. The particle produces a new copy to the left. The multiset \\{D(2), D(3)\} is of size two.
import java.io.*;
import java.util.*;
import java.math.*;
import java.math.BigInteger; 
//import javafx.util.*; 
public final class B
{    
	static StringBuilder ans=new StringBuilder();
	static FastReader in=new FastReader();
	static ArrayList<ArrayList<Integer>> g,CARS,intersection;	
	static long mod=1000000007;
	static int D1[],D2[],par[];
	static boolean set[];
	static long INF=Long.MAX_VALUE;
	static long dp_R[][],dp_L[][];
	public static void main(String args[])throws IOException
	{  		
		int T=i();
		while(T-->0)
		{
			int N=i(),K=i();
			dp_L=new long[N][K+1];
			dp_R=new long[N][K+1];
			for(int i=0; i<N; i++)
			{
				Arrays.fill(dp_L[i], -1);
				Arrays.fill(dp_R[i], -1);
			}
			System.out.println(f(0,K,true));

		}
	}
	static long f(int index,int K,boolean f)
	{
		if(K==1)return 1;
		boolean l=true,r=true;
		if(index==0)l=false;
		if(index+1==dp_L.length)r=false;		
		if(f)
		{
			//dp_R will be used
			if(dp_R[index][K]==-1)
			{
				long a=1,b=1;
				if(r)a=f(index+1,K,f);
				if(l)b=f(index-1,K-1,f^true);
				dp_R[index][K]=(a%mod+b%mod)%mod;
			}
			return dp_R[index][K];
		}
		else
		{
			if(dp_L[index][K]==-1)
			{
				long a=1,b=1;
				if(r)a=f(index+1,K-1,f^true);
				if(l)b=f(index-1,K,f);
				dp_L[index][K]=(a%mod+b%mod)%mod;
			}
			return dp_L[index][K];
		}
	}
	static boolean isValid(char X[],int l,int N)
	{
		int r=N-l; r--;
		//System.out.println(l+" "+r);
		if(r>=(l+1))
		{
			for(int i=0; i<=l; i++)
			{
				if(X[i]!=X[i+l+1])return false;
			}
			return true;
		}
		return false;
	}
	static boolean ispalin(char X[],int l,int r)
	{
		while(l<r)
		{
			if(X[l]!=X[r])return false;
			l++; r--;
		}
		return true;
	}

	static long min(long a,long b,long c)
	{
		return Math.min(a, Math.min(c, b));
	}
	static void dfs(int n)
	{
		set[n]=true;
		for(int c:g.get(n))
		{
			if(!set[c])dfs(c);
		}
	}
	static void print(int a)
	{
		System.out.println("! "+a);
	}
	static int ask(int a,int b)
	{
		System.out.println("? "+a+" "+b);
		return i();
	}
	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]; //transfers the size
			par[b]=a;       //changes the parent
		}
	}
	static ArrayList<Integer> IND(int B[],HashMap<Integer,Integer> mp)
	{
		ArrayList<Integer> A=new ArrayList<>();
		for(int i:B)
		{
			if(mp.containsKey(i))
			{
				A.add(i);
				int f=mp.get(i)-1;
				if(f==0)
					mp.remove(i);
				else mp.put(i, f);		
			}
		}
		return A;
	}
	static HashMap<Integer,Integer> hash(int A[],int index)
	{
		HashMap<Integer,Integer> mp=new HashMap<Integer,Integer>();
		for(int i=index; i<A.length; i++)
		{
			int f=mp.getOrDefault(A[i], 0)+1;
			mp.put(A[i], f);
		}
		return mp;
	}
	static void swap(char A[],int a,int b)
	{
		char ch=A[a];
		A[a]=A[b];
		A[b]=ch;
	}

	static long lower_Bound(long A[],int low,int high, long 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 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 void setGraph(int N)
	{
		g=new ArrayList<ArrayList<Integer>>();
		intersection=new ArrayList<ArrayList<Integer>>();
		CARS=new ArrayList<ArrayList<Integer>>();
		for(int i=0; i<=N; i++)
		{
			CARS.add(new ArrayList<Integer>());
			intersection.add(new ArrayList<Integer>());
			g.add(new ArrayList<Integer>());

		}
	}

	static  long pow(long a,long b)
	{
		long mod=1000000007;
		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 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 long GCD(long a,long b) 
	{
		if(b==0)
		{
			return a;
		}
		else return GCD(b,a%b );
	}

	//Debugging Functions Starts

	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(ArrayList<Integer> A)
	{
		for(int a:A)System.out.print(a+" ");
		System.out.println();
	}

	//Debugging Functions END
	//----------------------
	//IO FUNCTIONS STARTS
	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 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;
	}

	//IO FUNCTIONS END

}
class pair {
	int k,index;
	boolean f;
	pair(int k,int index,boolean f)
	{
		this.k=k;
		this.index=index;
		this.f=f;
	}
}

//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());
	}
	//gey
	double nextDouble()
	{
		return Double.parseDouble(next());
	}

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

}