TLE in SQRROOT

Algorithm is good, initial value (estimate) is bad.
Generate some random cases (800 digits!) print out the single approximations while finding the root.
Then do some experimenting with the initial value and you'll get AC.

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]

The decimal module is too slow for that kind of implementation.
Read hendriks comment below the problemset carefully.