Pay attention to the small memory limit in this problem.

The computers of the Apollo moon landing rockets had 71 kilobytes of RAM. In this problem, you will have more at your disposal, a total of 4 MB of memory, and your task will be simpler: you must check whether the given input word is a palindrome. We remind you that a palindrome is a word that reads the same from left to right as it does from right to left, for example, kajak or inni.

To make it not too simple, in some tests, the length of the word will not be known before reading it.

Input

The first line of the input contains a single number $n$. In some test groups, this will be a positive number – in such a case, it denotes the length of the word that will be provided in the second line. In other test groups, $n = 0$, which means that you must read the word from the input without knowing its length beforehand.

The second line contains the word to be checked, consisting of lowercase English letters. This word is not empty, and its length does not exceed $20\,000\,000$ characters.

You may assume that in each test group, either all tests have $n > 0$, or in all of them $n = 0$.

Output

You should print a single line containing TAK or NIE depending on whether the given word is a palindrome.

Examples

Input 1

5
kajak

Output 1

TAK

Input 2

0
kanu

Output 2

NIE