For each integer i from 1 to n, you must print a string s_{i} of length n consisting of lowercase Latin letters.
The string s_{i} must contain exactly i distinct palindrome substrings.
Two substrings are considered distinct if they are different as strings.
Input
The input contains one integer n (1 ≤ n ≤ 2000).
Output
You must print n lines. If for some i, the answer exists, print it in the form “i : s_{i}” where s_{i} is one of possible strings.
Otherwise, print “i : NO”.
Sample
input  output 

4
 1 : NO
2 : NO
3 : abca
4 : bbca

Problem Author: Mikhail Rubinchik
Problem Source: Ural FU Dandelion contest. Petrozavodsk training camp. Summer 2014