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

1248

Sample Output

T.^T

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

        要用unsigned long long

#include <iostream>#include <stdio.h>#include <string.h>using namespace std;unsigned long long a[10000];unsigned long long n;int main(){    string str = "T.T^__^";    memset(a,0,sizeof(a));    a[0] = 4;    a[1] = 3;    for(int i = 2; i < 10000; i++)        a[i] = a[i - 1] + a[i - 2];    while(cin>>n)    {        while(n > 7)        {            int i = 0;            while(a[i]<n)                i++;            n -= a[i-1];        }        cout<<str[n-1]<<endl;;    }    return 0;}