来源：http://acm.hdu.edu.cn/contests/contest_showproblem.php?cid=843&pid=1003

Problem Description

通常来说，题面短的题目一般都比较难，所以我要把题面写得很长很长。
通常来说，题面短的题目一般都比较难，所以我要把题面写得很长很长。
通常来说，题面短的题目一般都比较难，所以我要把题面写得很长很长。
鸽子数字由以下过程定义：从任何正整数开始，将数字替换为其各个数位的平方和，并重复该过程，直到该数字等于1。如果不能，则这个数字不是鸽子数。
例如7是鸽子数，因为7->49->97->130->10->1。（7*7=49,4*4+9*9=97,9*9+7*7=130....如此类推）
显然1是第一个鸽子数。
有Q个询问，每个询问给出一个数k，你需要输出第k个鸽子数。

 

 

Input

第一行一个Q，代表询问的个数（Q<=100000）
接下来Q行，每行一个数字k（k<150000）

 

 

Output

每行输出一个数，代表第k个鸽子数

 

 

Sample Input


 

2 1 2

 

 

Sample Output


 

1 7

思路：打表

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<set>
#include<algorithm>
using namespace std;
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);
const int N = 150000 +2;
const int mod = 1000000007;
int a[N];
void init()
{
    int n,t,cnt=0;
    for(int i =1; cnt <=150000; i++)
    {
        n=i;
        while(n!=1&&n!=4)
        {
            t=0;
            while(n)
            {
                t+=(n%10)*(n%10);
                n/=10;
            }
            n=t;
            if(n==1)
                a[cnt++]=i;
        }
    }
}
#define ll long long int
int main()
{
//   freopen("C:\\Users\\nuoyanli\\Desktop\\acminput.txt","r",stdin);
//   freopen("C:\\Users\\nuoyanli\\Desktop\\acminput.txt","r",stdout);
    int x,num;
    init();
    IOS;cin>>num;
    while(num--)
    {
        cin>>x;
        if(x==1)
            cout<<"1\n";
        else
            cout<<a[x-2]<<"\n";
    }
    return 0;
}