Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
The Cubic End
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 1374Accepted: 666

Description

Given any string of decimal digits, ending in 1, 3, 7 or 9, there is always a decimal number, which when cubed has a decimal expansion ending in the original given digit string. The number need never have more digits than the given digit string.

Write a program, which takes as input a string of decimal digits ending in 1, 3, 7 or 9 and finds a number of at most the same number of digits, which when cubed, ends in the given digit string.

Input

The input begins with a line containing only the count of problem instances, nProb, as a decimal integer, 1 nProb 1000. This is followed by nProb lines, each of which contains a string of between 1 and 10 decimal digits ending in 1, 3, 7 or 9.

Output

For each problem instance, there should be one line of output consisting of the number, which when cubed, ends in the given digit string. The number should be output as a decimal integer with no leading spaces and no leading zeroes.

Sample Input

4
123
1234567
435621
9876543213

Sample Output

947
2835223
786941
2916344917

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator