You are given two integers n and k.

Your task is to construct such a string s of length n that for each i from 1 to k there is at least one i-th letter of the Latin alphabet in this string (the first letter is 'a', the second is 'b' and so on) and there are no other letters except these. You have to maximize the minimal frequency of some letter (the frequency of a letter is the number of occurrences of this letter in a string). If there are several possible answers, you can print any.

You have to answer t independent queries.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 100) — the number of queries.

The next t lines are contain queries, one per line. The i-th line contains two integers n_i and k_i (1 ≤ n_i ≤ 100, 1 ≤ k_i ≤ min(n_i, 26)) — the length of the string in the i-th query and the number of characters in the i-th query.

Output

Print t lines. In the i-th line print the answer to the i-th query: any string s_i satisfying the conditions in the problem statement with constraints from the i-th query.

Example

Input


3
7 3
4 4
6 2


Output


cbcacab
abcd
baabab

Note

In the first example query the maximum possible minimal frequency is 2, it can be easily seen that the better answer doesn't exist. Other examples of correct answers: "cbcabba", "ccbbaaa" (any permutation of given answers is also correct).

In the second example query any permutation of first four letters is acceptable (the maximum minimal frequency is 1).

In the third example query any permutation of the given answer is acceptable (the maximum minimal frequency is 3).
	import java.io.BufferedWriter;
	import java.io.IOException;
	import java.io.InputStream;
	import java.io.OutputStream;
	import java.io.OutputStreamWriter;
	import java.io.PrintWriter;
	import java.io.Writer;
	import java.util.Arrays;
	import java.util.InputMismatchException;
	import java.util.*;
	import java.io.*;
	import java.math.*;
	public class Main{

	static class Pair
		{ 
			int x; 
			int y; 
			// Constructor 
			public Pair(int x, int y) 
			{	 
				this.x = x; 
				this.y = y; 
			}	 
		} 
		static class Compare
		{ 
			static void compare(Pair arr[], int n) 
			{ 
				// Comparator to sort the pair according to second element 
				Arrays.sort(arr, new Comparator<Pair>() { 
					@Override public int compare(Pair p1, Pair p2) 
					{ 
						return p1.y - p2.y; 
					} 
				}); 
			} 
		}
		public static long pow(long a, long b)
		{
			long result=1;
			while(b>0)
			{
				if (b % 2 != 0)
				{
					result=(result*a);
					b--;
				} 
				a=(a*a);
				b /= 2;
			}   
					return result;
		}
		public static BigInteger fact(long num)
		{
					BigInteger fact=new BigInteger("1");
					int i=0;
					for(i=1; i<=num; i++)
					{
						BigInteger bg=BigInteger.valueOf(i);
						fact=fact.multiply(bg);
					}
					return fact;
				}
				public static long gcd(long a, long b)
				{
					if (a == 0)
						return b;
					return gcd(b%a, a);
				}
				
				public static long lcm(int a,int b)
				{
					return a * (b / gcd(a, b));
				}
				public static long sum(int h)
				{
					return (h*(h+1)/2);
				}
			/*	public static void dfs(int parent,boolean[] visited)
				{
					ArrayList<Integer> arr=new ArrayList<Integer>();
					arr=graph.get(parent);
					visited[parent]=true;
					bigParent=parent;
					for(int i=0;i<arr.size();i++)
					{
						int num=arr.get(i);
						if(visited[num]==false)
						{
							color[num]=count++;
							dfs(num,visited);
						}
					}
				}
				static int count=0;
				static int[] storing1;
			*/	static int[] storing2;
				static ArrayList<ArrayList<Integer>> graph;
				public static void main(String args[])throws IOException
				{
					InputReader in=new InputReader(System.in);
					OutputWriter out=new OutputWriter(System.out);
				//	long a=pow(26,1000000005);
				//    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
					ArrayList<Integer> ar=new ArrayList<>();
					ArrayList<Integer> ar1=new ArrayList<>();
					ArrayList<Integer> ar2=new ArrayList<>();
					ArrayList<Integer> ar3=new ArrayList<>();
					ArrayList<Integer> ar4=new ArrayList<>();
					TreeSet<Integer> ts=new TreeSet<>();
					TreeSet<Integer> ts1=new TreeSet<>();
					HashMap<Integer,Integer> hash=new HashMap<Integer,Integer>();
					HashMap<Long,Integer> hash1=new HashMap<Long,Integer>();
					HashMap<Long,Integer> hash2=new HashMap<Long,Integer>();
					boolean[] prime=new boolean[100001];
					for(int i=2;i*i<=100000;i++)
					{
						if(prime[i]==false)
						{
							for(int j=2*i;j<=100000;j++)
							{
								prime[j]=true;
							}
						}
					}
					int t=i();
					while(t-->0)
					{
						int n=i();
						int k=i();
						int flag=0;
						for(int i=0;i<k;i++)
						{
							System.out.print((char)('a'+i)+"");
						}
						flag+=k;
						while(flag<n && flag+k<=n)
						{
							for(int i=k;i<2*k;i++)
							{
								System.out.print((char)('a'+i-k)+"");
							}
							flag+=k;
						}
						if(flag<n)
						{
							for(int i=flag;i<n;i++)
							{
								System.out.print((char)('a'+i-flag)+"");
							}
						}
						pln("");
					}
				}
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				/**/
				static InputReader in=new InputReader(System.in);
					static OutputWriter out=new OutputWriter(System.out);
					public static long l()
					{
						String s=in.String();
						return Long.parseLong(s);
					}
					public static void pln(String value)
					{
						System.out.println(value);
					}
					public static int i()
					{
						return in.Int();
					}
					public static String s()
					{
						return in.String();
					}
		}
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			class InputReader {
				 
				private InputStream stream;
				private byte[] buf = new byte[1024];
				private int curChar;
				private int numChars;
				private SpaceCharFilter filter;
			 
				public InputReader(InputStream stream) {
					this.stream = stream;
				}
			 
				public int read() {
					if (numChars== -1)
						throw new InputMismatchException();
					if (curChar >= numChars) {
						curChar = 0;
						try {
							numChars = stream.read(buf);
						} catch (IOException e) {
							throw new InputMismatchException();
						}
						if (numChars <= 0)
							return -1;
					}
					return buf[curChar++];
				}
			 
				public int Int() {
					int c = read();
					while (isSpaceChar(c))
						c = read();
					int sgn = 1;
					if (c == '-') {
						sgn = -1;
						c = read();
					}
					int res = 0;
					do {
						if (c < '0' || c > '9')
							throw new InputMismatchException();
						res *= 10;
						res += c - '0';
						c = read();
					} while (!isSpaceChar(c));
					return res * sgn;
				}
			 
				public String String() {
					int c = read();
					while (isSpaceChar(c))
						c = read();
					StringBuilder res = new StringBuilder();
					do {
						res.appendCodePoint(c);
						c = read();
					} while (!isSpaceChar(c));
					return res.toString();
				}
			 
				public boolean isSpaceChar(int c) {
					if (filter != null)
						return filter.isSpaceChar(c);
					return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
				}
			 
				public String next() {
					return String();
				}
			 
				public interface SpaceCharFilter {
					public boolean isSpaceChar(int ch);
				}
			}
			 
			class OutputWriter {
				private final PrintWriter writer;
			 
				public OutputWriter(OutputStream outputStream) {
					writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
				}
			 
				public OutputWriter(Writer writer) {
					this.writer = new PrintWriter(writer);
				}
			 
				public void print(Object...objects) {
					for (int i = 0; i < objects.length; i++) {
						if (i != 0)
							writer.print(' ');
						writer.print(objects[i]);
					}
				}
			 
				public void printLine(Object...objects) {
					print(objects);
					writer.println();
				}
			 
				public void close() {
					writer.close();
				}
			 
				public void flush() {
					writer.flush();
				}
			 
				}
			 
				class IOUtils {
			 
				public static int[] readIntArray(InputReader in, int size) {
					int[] array = new int[size];
					for (int i = 0; i < size; i++)
						array[i] = in.Int();
					return array;
				}
			 
				} 