SUMDEC2 - Sum the Decimal-part II

A much easier version of this problem can be found here-SUMDEC1. In case you haven't tried it out, try the first part.

In this problem, you are given a number. You need to output the sum of the first 1000 decimal places of the square-root of the number (ignore the integral part).

For example-if the given number is 2. The square-root of 2 is 1.4142135623..... So, ignore the number before decimal (1 in this case) and add the first 1000 digits after decimal and output them as result. (4482 in this case.

NOTE-If the number is a perfect square, the output should be 0.

Input

the first line of input consist of t (the number of test cases).
t lines follow-Each line consist of a non-negative integer n.

Output

Output in separate lines the result corresponding to integer n.

Constraints

1 <= t <= 100
1 <= n <= 100000

Example

Input:
2
4
2

Output:
0
4482

Added by:Prateek Agarwal
Date:2016-01-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY

hide comments
2017-10-05 08:43:24
No newline after last result gives WA. WTF!
2017-09-18 20:46:33 Pranay
cake walk in python
2016-01-25 15:40:42
TAKE PRECISION 2-3 RANK BIGGER THAN 100000
MY 11
2016-01-22 09:13:13
testcase:-
27138
99892
answer please.

Last edit: 2016-01-22 09:15:33
2016-01-12 14:31:30 sairampola
getting NZEC in python 2.7 .. can u check the input ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.