SQRROOT - Square Root

no tags 

In this problem you have to find the Square Root for given number. You may assume that such a number exist and it will be always an integer.

Solutions to this problem can be submitted in C, C++, Pascal, Algol, Fortran, Ada, Ocaml, Prolog, Whitespace, Brainf**k and Intercal only.

Input

t - the number of test cases [t <= 50]
then t positive numbers follow, each of them have up to 800 digits in decimal representation.

Output

Output must contain exactly t numbers equal to the square root for given numbers. See sample input/output for details.

Example

Input:
3
36
81
226576

Output:
6
9
476

hide comments
mahilewets: 2017-08-29 21:39:23

Python decimal module.

riu_20: 2017-03-15 17:47:11

Greeeeen finally!! phewwwww! :D

ragwave: 2016-07-04 20:16:25

implementation is bit tough in C++.Enjoyed solving!!! :)

Mohit Rathore: 2016-01-23 14:46:31

@pvkcse use babylonian method. Python ACed at 0.15 sec

dheerajm: 2015-07-11 15:39:52

Are there any boundary cases for this question?
I have implemented digit by digit method taught in school but still it shows wrong answer. I have checked many test cases (upto 100) it gave correct answer for all of these. Please can anybody help me..

Anubhav Balodhi : 2015-01-18 10:36:35

got AC finally... good question ^_^

Last edit: 2015-01-18 10:36:47
Naman Goyal: 2014-05-28 07:36:53

Used digit by digit method taught in grade school. Got AC in C in 0.22 sec.

pvkcse: 2014-05-16 20:14:57

Newton method in python got AC but at 2.41s...Any fastest algo...???

Chandan Mittal: 2013-05-15 20:55:42

i hav used NEWTON-RAPHSON approximation method..
chk here
http://ideone.com/oquaF9

getting TLE :( :(
my code works till 10^50 but fails beyond 10^60
can any1 pls help optimizing the approach..

Last edit: 2013-05-15 21:28:25
Sohinee Basak: 2012-06-05 10:49:28

Last edit: 2012-06-16 16:43:49

Added by:Roman Sol
Date:2004-12-15
Time limit:0.781s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: BASH CSHARP CLPS LISP sbcl LISP clisp ERL HASK ICON JAVA JS-RHINO LUA NEM NICE PERL PHP PIKE PYTHON RUBY SCM qobi ST
Resource:ZCon 2005