该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

在 XJSOJ Games（XJS星球） 中，数字游戏是非常普遍的。回音之数（ The number of echoes ） 是 XJS Games 中吉祥最喜欢玩的一款热门游戏。在这个游戏中会有一种神秘的魔法数字，它们深受人们的喜爱，因为其象征晨曦与黄昏的平衡，而且这还将是游戏通关的密码。

题目描述

一个回音之数，就是一个从前往后读与从后往前读完全相同的整数。简而言之，它就是一个回文数。

示例：

✔️是回音之数：$121、242、1331、1001、77777$

❌不是回音之数：$123、3401、20510、9876$

在魔法中的数学领域，吉祥发现任意一个正整数都能用两个回音之数相加表示。然而，每个数的拆解方式是不同的，可能有多种表示方法。

例如：

$142 = 131 + 11$

$313 = 292 + 21 = 111 + 202$

$500 = 494 + 6 = 252 + 248$

这种性质让玩家们相信，回音之数的组合方式隐藏着 XJS星球 的某种宇宙法则。

在 XJS Games 中有一个难题。预言家提到：“当世界之数归于和谐，晨曦与黄昏才能再度交汇。” 这意味着，找到一个数 ( $n$ ) 可以用多少种方式拆解成两个回音之数之和，或许能揭示出平衡破裂的真相。

于是，玩家们向吉祥提出了这道问题：

• 对于给定的数 ( $n$ )，计算它能用多少种不同的两个回音之数之和表示。

这不仅仅是一个数学问题，而是吉祥和玩家们在 XJS Games 命运的关键。然而，吉祥无法在短时间内解决这个问题，所有，他找到了会 C++ 的你，希望你可以帮助他解决这个问题。

输入格式

本题有多组数据。

第一行一个正整数 $T$ 表示数据组数。

下面 $T$ 行，每行一个正整数 $n$。

输出格式

对于每组数据，输出一行一个整数表示答案。

样例

样例

4
256
42658
999999999999999999999999999999999999999999999999999999
988888888888888888888888888888888888888888888888888977

4
4
800000000000000000000000000
635634

样例解释

对于第一组数据，满足条件的方案有：

• $(4,252)$
• $(44,212)$
• $(212,44)$
• $(252,4)$

对于第二组数据，满足条件的方案有：

• $(434,42224)$
• $(5995,36663)$
• $(36663,5995)$
• $(42224,434)$

对于第三组数据，输入是 $10^{54}-1$，输出是 $8 \times 10^{26}$。

数据范围

本题包含 $100$ 个测试点，每个测试点的数据范围不尽相同，但你必须通过所有测试点才能得分。

对于 $100\%$ 的数据，$1 \le T \le 10^4$，$1 \le n \le 10^{54}$。