TLE 好幾次 改進算法過了
//====================================================================||
// ||
// ||
// Author : GCA ||
// 6AE7EE02212D47DAD26C32C0FE829006 ||
//====================================================================||
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cctype>
#include <utility>
using namespace std;
#ifdef ONLINE\_JUDGE
#define ll "%lld"
#else
#define ll "%I64d"
#endif
typedef unsigned int uint;
typedef long long int Int;
#define Set(a,s) memset(a,s,sizeof(a))
#define Write(w) freopen(w,"w",stdout)
#define Read(r) freopen(r,"r",stdin)
#define Pln() printf("\\n")
#define I\_de(x,n)for(int i=0;i<n;i++)printf("%d ",x\[i\]);Pln()
#define De(x)printf(#x"%d\\n",x)
#define For(i,x)for(int i=0;i<x;i++)
#define CON(x,y) x##y
#define Pmz(dp,nx,ny)for(int hty=0;hty<ny;hty++){for(int htx=0;htx<nx;htx++){\\
printf("%2d ",dp\[htx\]\[hty\]);}Pln();}
#define M 55
#define PII pair<int,int\>
#define PB push\_back
#define oo INT\_MAX
#define Set\_oo 0x3f
#define Is\_debug true
#define debug(...) if(Is\_debug)printf("DEBUG: "),printf(\_\_VA\_ARGS\_\_)
#define FOR(it,c) for(\_\_typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define eps 1e-6
bool xdy(double x,double y){return x>y+eps;}
bool xddy(double x,double y){return x>y-eps;}
bool xcy(double x,double y){return x<y-eps;}
bool xcdy(double x,double y){return x<y+eps;}
int min3(int x,int y,int z){
int tmp=min(x,y);
return min(tmp,z);
}
int max3(int x,int y,int z){
int tmp=max(x,y);
return max(tmp,z);
}
struct bignum{
Int n\[201\];
static const int maxn=201;
static const Int base\=10000;
bignum(){
Set(n,0);
}
bignum operator\-(bignum &d){
bignum ans;
Int c=0;
for(int i=0;i<maxn;i++){
Int tmp=n\[i\]-d.n\[i\]-c;
if(tmp<0){
c=1;
ans.n\[i\]=tmp+base;
}else{
c=0;
ans.n\[i\]=tmp;
}
}
return ans;
}
bool operator<(bignum &d){
for(int i=maxn-1;i>=0;i--){
if(n\[i\]<d.n\[i\])return true;
else if(n\[i\]>d.n\[i\])return false;
}return false;
}
bool operator\>=(bignum &d){
for(int i=maxn-1;i>=0;i--){
if(n\[i\]>d.n\[i\])return true;
else if(n\[i\]<d.n\[i\])return false;
}return true;
}
bool operator\>(bignum &d){
for(int i=maxn-1;i>=0;i--){
if(n\[i\]>d.n\[i\])return true;
else if(n\[i\]<d.n\[i\])return false;
}return false;
}
bignum operator+(bignum &d){
bignum ans;
Int c=0;
for(int i=0;i<maxn;i++){
Int tmp=n\[i\]+d.n\[i\];
ans.n\[i\]=tmp%base;
c=tmp/base;
}
}
bignum mul(Int x){
bignum ans;
Int c=0;
for(int i=0;i<maxn;i++){
Int tmp=n\[i\]\*x;
ans.n\[i\]=tmp;
}
for(int j=0;j<maxn;j++){
Int tmp=ans.n\[j\]+c;
ans.n\[j\]=tmp%base;
c=tmp/base;
}
return ans;
}
bignum add(Int x){
bignum ans;
Int tmp=n\[0\]+x,c;
ans.n\[0\]=tmp%base;
c=tmp/base;
for(int i=1;i<maxn;i++){
Int tmp=n\[i\]+c;
ans.n\[i\]=tmp%base;
c=tmp/base;
}
return ans;
}
void print(){
int i=maxn-1;
for(;i>0;i--)if(n\[i\])break;
printf("%lld",n\[i--\]);
for(;i>=0;i--)printf("%04lld",n\[i\]);
Pln();
}
};
char str\[1005\];
int len;
int test;/\*
int vfind(bignum a,int target){
int l=0,r=9;
while(r>=l){
int mid=(r+l)>>1;
bignum tmp=a.mul(10);
tmp=tmp.add(mid);
tmp=tmp.mul(mid);
//tmp.print();
if(tmp>target){
r=mid-1;
}else if(tmp<target){
l=mid+1;
}
else return mid;
}//Pln();
return r;
}\*/
void sqrt(){
vector<int\> sp;
int t=0;
for(int i=len-1,j=0;i>=0;i--){
if(j==0){
t+=str\[i\]-'0';
j++;
}else if(j==1){
t+=(str\[i\]-'0')\*10;
j++;
}if(j==2||i==0){
//debug("%d\\n",t);
sp.PB(t);
t=j=0;
}
}
int size=sp.size();
for(int i=0;i<size/2;i++){
int t=sp\[i\];
sp\[i\]=sp\[size-i-1\];
sp\[size-i-1\]=t;
}
bignum odd,ans,re;
for(int i=0;i<size;i++){
odd=ans.mul(20);
odd=odd.add(1);
re=re.mul(100);
re=re.add(sp\[i\]);
int j=0;
for(j=0;re>=odd;j++){
re=re-odd;
odd=odd.add(2);
}
ans=ans.mul(10);
ans=ans.add(j);
/\*debug("%d\\n",sp\[i\]);
odd.print();
re.print();
ans.print();
Pln();\*/
}
ans.print();
/\*for(int i=0;i<size;i++){
// printf("sp>>%d\\n",sp\[i\]);
//now=now.mul(100);
//now=now.add(sp\[i\]);
now\*=100;
now+=sp\[i\];
//now.print();
//printf(">>a");a.print();
int index=vfind(a,now);
//printf(">>%d\\n",index);
ans\[i\]=index+'0';
bignum tmp=a.mul(10);
tmp=tmp.add(index);
tmp=tmp.mul(index);
//printf("tmp");tmp.print();
now=now-tmp;
//printf("now");now.print();
b=a.mul(10);
b=b.add(index);
a=b.add(index);
}\*/
}
int main(){
//freopen("input.txt","r",stdin);
ios\_base::sync\_with\_stdio(0);
scanf("%d",&test);
while(test--){
bignum inp;
scanf("%s",str);
// debug("%s\\n",str);
len=strlen(str);
sqrt();
if(test)Pln();
// inp=inp.add(111);
// inp=inp.mul(100);
// (inp.add(0)).print();
}
}