Problem E
Samhverfudulritun

Sigga has been following the progress on quantum computers. She feels a bit threatened since they might break RSA encryption, which is based on primes, and is widely used to encrypt messages on the internet today. If this encryption system hasn’t been replaced when the first real quantum computer sees the light of day, no one will be safe on the internet!

Sigga takes this very seriously and decides to make her own encryption protocol. Instead of using primes she decides to use palindromes. A number is a palindrome if it’s the same read forwards and backwards. For example 5, 11, 121 and 9779 are palindromes.

To check the safety of the encryption protocol she needs a list of palindromes of different sizes. She asks you to find, for each $k$ between $1$ and $100$, the largest palindrome that isn’t greater than $2^k$.

Input

There is no input.

Output

For each $k$ between $1$ and $100$ there can be one line containing two integers: $k$ and the largest palindrome not exceeding $2^k$. The lines can be printed in any order and not all $k$ have to be printed (but more is better).

Scoring

The solution gets one point for each $k$ in the output that’s correct.

Explanation of Sample Inputs

The sample output contains five lines, one for each $k$ in $\{ 1,4,3,10,6\} $. Here we see that there isn’t a line for each $k$ between $1$ and $100$, but only for $5$ numbers. When $k = 4$ the second number should be the largest palindrome not exceeding $2^4 = 16$, but that’s exactly $11$. A solution printing this thus gets one point for $k = 4$. In the same way we see that it would get three more points for $k$ in $\{ 1, 3, 10\} $. For $k = 6$ the second number should be the largest palindrome not exceeding $2^6 = 64$ but the output is $44$ while the answer is $55$ for this $k$. Thus the solution gets no point for this $k$. In total a solution printing this would get $4$ points.

1 2
4 11
3 8
10 1001
6 44