We will construct an infinitely long string from two short strings: A = "^__^" (four characters), and B = "T.T" (three characters). Repeat the following steps:

• Concatenate A after B to obtain a new string C. For example, if A = "^__^" and B = "T.T", then C = BA = "T.T^__^".
• Let A = B, B = C -- as the example above A = "T.T", B = "T.T^__^".

Your task is to find out the n-th character of this infinite string.

Input

The input contains multiple test
cases, each contains only one integer N (1 <= N <= 2^63 - 1).
Proceed to the end of file.

Output

For each
test case, print one character on each line, which is the N-th (index
begins with 1) character of this infinite string.

Sample Input

1

2

4

8

Sample Output

T

.

^

T

题意：不断循环   找出第N个字母是什么  输出

要用unsigned long long

#include <iostream>

#include <stdio.h>

#include <string.h>

using namespace std;

unsigned long long a[];

unsigned long long n;

int main()

{

    string str = "T.T^__^";

    memset(a,,sizeof(a));

    a[] = ;

    a[] = ;

    for(int i = ; i < ; i++)

        a[i] = a[i - ] + a[i - ];

    while(cin>>n)

    {

        while(n > )

        {

            int i = ;

            while(a[i]<n)

                i++;

            n -= a[i-];

        }

        cout<<str[n-]<<endl;;

    }

    return ;

}