Elma's Chessboard Journey

Elma is learning chess. Her grandmother has given her a challenging task: starting from square (a1) on a standard 8(\times)8 chessboard, she must reach square (h8) in exactly (n) moves. In each move, Elma can move like a rook, that is, she may move any positive number of squares either horizontally or vertically. However, she is not allowed to visit any square more than once.

Formally, given an integer (n) (where (2 \le n \le 63)), find a sequence of (n+1) distinct squares (s_1, s_2, \ldots, s_{n+1}) (in chess notation) such that:

• (s_1 = a1) and (s_{n+1} = h8).
• For each (1 \le i \le n), the move from (s_i) to (s_{i+1}) is strictly horizontal or vertical (i.e. they share the same row or the same column).
• No square appears more than once in the sequence.

Your program should output any valid route satisfying these conditions. The answer is guaranteed to exist for every (n) in the range.

inputFormat

A single integer (n) ((2 \le n \le 63)).

outputFormat

Output a sequence of (n+1) space‐separated chessboard positions (using standard algebraic notation, e.g. a1, b5, etc.) representing a valid route from (a1) to (h8) following the rules.

sample

2

a1 a8 h8