Description

假定有n个元素的集合，集合元素分别用a,b,c,d....表示。请你输出所有的非空子集（即子集但不包括空集）。

教程：有n个元素的集合，可以用一个n位的二进制数表示，每一位对应一个集合的元素，当前位置是0或1分别表示这个元素没选中或者选中。 假定集合有3个元素，那么用三位二进制数000~111表示所有组合，因此共有8总组合，其中000表示空集。111表示它本身。

cba

000->空集

001->a

010->b

011->ba

100->c

101->ca

110->cb

111->cba

Input

输入多组数据，每组数据的第一行是一个整数n，表示集合内元素的个数（n<=10）

Output

每组数据输出多行，每行表示一种组合的情况，用一个只包含小写字母的字符串表示集合，集合内的元素从大到小排序。按照字典序从小到大输出所有的组合情况。 每组案例之间用一个空行隔开。 具体参考样例

Samples

1

a

3

a
b
ba
c
ca
cb
cba

Limitation

1s, 1024KiB for each test case.