Remember the pyramid problem from PL1 where you need to print a pyramid with ‘*’ characters? We got the same problem here with 2 types of pyramids. In the images below there are two types of pyramids with 4 steps. The first type is top to bottom and the second type is its reverse.

Now given the number of steps N and the type T print a type T pyramid with N steps.

Input

Input starts with an integer X (≤ 50), denoting the number of test cases.

Each case contains two integers N and T where N (1 ≤ N ≤ 20) denotes the number of steps and T (1 ≤ T ≤ 2) denotes the type of the pyramid.

Output

For each test case print N lines containing only ‘*’ and required spaces to form the pyramid. Do not print extra unnecessary characters.

Example

Input:
2
3 2
4 1

Output:
*****
 ***
  *
   *
  ***
 *****
*******