Hash Code Hacker

According to the Java standard library documentation, the hash code of a string is computed as

$s[0] \times 31^{n-1} + s[1] \times 31^{n-2} + \cdots + s[n-1]$

where $s[i]$ is the $i$-th character of the string and $n$ is the length of the string. The computation uses signed 32-bit two's complement integers, so an overflow keeps only the low 32 bits.

Heather wants to attack the servers of a company. The attack needs $k$ distinct query strings whose hash codes are all equal. The servers accept query strings made of uppercase and lowercase English letters only.

Write a program that builds such query strings for Heather.

The single line contains the number of query strings to build, $k$ ($2 \le k \le 1000$).

Print $k$ query strings, one per line. Each query string is non-empty, has length at most 1000, and consists of uppercase and lowercase English letters only. The $k$ strings are pairwise distinct and their hash codes are all equal.

Many answers satisfy those conditions, so this version fixes one of them for judging. Let $m$ be the smallest non-negative integer with $2^m \ge k$. For each $i = 0, 1, \ldots, k-1$, write $i$ in binary using exactly $m$ digits with leading zeros, then replace every digit 0 with Aa and every digit 1 with BB. Print the resulting strings in increasing order of $i$.

In the hash computation of a two character block, Aa and BB both give the value $2112$, so the $k$ strings built by this rule share the same length $2m$ and the same hash code. Since $k \le 1000$, we have $m \le 10$ and the length never exceeds 20.