Для каждого целого положительного числа i от 1 до n выдайте строку длины n из букв «a» и «b», содержащую ровно i различных подстрок-палиндромов. Две подстроки считаются различными, если они различаются как строки.

На вход подаётся целое число n (1 ≤ n ≤ 2000).

На выходе ожидается n строк. Каждая строка должна иметь вид: «i : s_i», где i — номер строки. Если для некоторого i не существует такой строки, вместо s_i следует выводить «NO».