Given an integer N which is the number of lines to be printed. Make a program that prints a triangle in the same format of the Example Output

Input Format:

In the first line only 1 integer N

Example 1

Input

3

Output

  *
 **
***

Example 2

Input

5

Output

    *
   **
  ***
 ****
*****

Example 3

Input

6

Output

     *
    **
   ***
  ****
 *****
******