You are given a number n. Print n lines, i-th line should consist of i characters "*". Lines' indices are 1-based.

Input

The only line of input contains an integer n (1 ≤ n ≤ 50).

Output

Output the described pattern.

Examples

Input

3


Output

*
**
***


Input

6


Output

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

Source: codeforces | Difficulty: EASY
Tags: Implementation


Solutions: