I'm too having TLE, I used the initial guesses as described on wiki page. Can you have a look at the code below pls.
[bbone=Python,295]
from decimal import *
T = int(input())
while(T):
with localcontext() as ctx:
ctx.prec = 800
Str = input()
S =Decimal(Str)
D = len(Str)
if D % 2 == 0:
n = int((D-2) / 2)
s0 = '6'
while(n):
s0 += '0'
n = n-1
x0 = Decimal(s0)
else:
n = int((D-1) / 2)
s0 = '2'
while(n):
s0 += '0'
n = n-1
x0 = Decimal(s0)
x = x0
x1 = x*x
while(x1.to_integral() != S):
x = (x + S / x) / 2
x1 = x * x
print (x.to_integral())
T = T-1
[/bbone]