Upside Down Numbers

An upside down number is one that appears the same when flipped 180 degrees. Given n, return all upside down numbers as strings whose length is n, sorted in lexicographic order.

Constraints

• n ≤ 15

https://binarysearch.com/problems/Upside-Down-Numbers

Examples

Example 1

Input

• n = 1

Output

• answer = ['0', '1', '8']

Example 2

Input

• n = 2

Output

• answer = ['11', '69', '88', '96']

Example 3

Input

• n = 3

Output

• answer = ['101', '111', '181', '609', '619', '689', '808', '818', '888', '906', '916', '986']

Solution