KZHAPPY - Happy Sequence

The Kruzade OPC team felt we should have a happy ending to the Kruzade online coding event. We define the happy sequence as follows: let the sum of the squares of the digits of a positive integer s0 be represented by s1. In a similar way, let the sum of the squares of the digits of s1 be represented by s2, and so on. If si=1 for some i>=1, then the original integer s0 is said to be happy. For example, starting with 7 gives the sequence 7, 49, 97, 130, 10, 1, so 7 is a happy number. The first few happy numbers are 1, 7, 10, 13, 19, 23, 28, 31, 32, 44, 49...

You have been hired to find out the nth happy number in the sequence.

Input

First line contains an integer T, representing the number of test-cases. Then T lines follow each containing one integer n, 1 <= n <= 500.

Output

For each test case output on a line the nth happy number in the sequence.

Example

Input:
3
10
5
20
Output: 44
19
100

Added by:balaji
Date:2009-09-19
Time limit:3.599s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 DOC ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PDF PERL PHP PIKE PS PRLG-swi PYTHON RUBY SCALA SCM guile SCM qobi ST TCL TEXT WHITESPACE
Resource:kruzade 09 practice

hide comments
2020-03-20 22:37:15
Indeed, it's a fun problem if one self-imposes a higher limit on n. My verbose 700b Python solution precomputes 150,000 terms in 1s.
2011-02-25 07:41:13 krishna kant
Till how long, it is to be checked for a particular number to be happy ?
2009-09-20 17:08:42 pankaj
i think you are right. I too agree with you. The limit is very less and we can calculate all the 500 values and just print it for given test case.
2009-09-20 16:43:21 hendrik
Shouldnt we have a much lower source limit here? Say 1k or so (or better 500B). I mean you could calc them all offline and use them as constants. Where is the challenge?

Last edit: 2009-09-20 17:27:28
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.