PALNUM - Palindromic Number

no tags 

A positive integer A is called a "palindrome number" if the reverse of the decimal representation is the same as the original one. For example 13231 is a palindrome number, but 13333 is not.

Given a number A (1 <= A <= 1e18), find the number of pairs (a, b) such that a and b are both palindrome numbers, and the sum of a and b is A.

If A is 391, there are 6 ways:

  • 8 + 383 = 391
  • 383 + 8 = 391
  • 88 + 303 = 391
  • 303 + 88 = 391
  • 99 + 292 = 391
  • 292 + 99 = 391

Input

The first Line contains the number of test cases T <= 10. Each test case contains a number A.

Output

Output the number of ways.

Example

Input:
1
391

Output:
6

hide comments
golovleo: 2022-05-05 19:32:38

AC in 1 go!
really just one for

sky_10: 2020-07-14 17:07:01

AC in 3 go !

Last edit: 2020-07-14 17:21:52
hodobox: 2019-11-21 16:14:07

0 is not a palindrome as the statement clearly states 'A *positive* integer A is called a palindrome number...'

roopammishra: 2019-01-09 19:09:58

Nice concept!! Ac in 3 go: ( ..and yeah '0' is not palindrome here!!

Last edit: 2019-01-09 19:11:59
mani_mckinnon: 2015-08-07 09:36:56

Easy

Tushar Sinha: 2015-01-01 13:40:21

it just keep on giving me TLE!!

Ðộc cô cầu bại: 2011-05-25 14:26:48

In this problem, 0 is not a palindrome. I have wrong answer just because of this.

Last edit: 2011-05-25 14:27:04

Added by:eleusive
Date:2008-10-04
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Al-Khawarizm 2008