题目描述

You are given a positive integer $A$. Find the number of factors of $A$ which are palindromes. A number is called a palindrome if it remains the same when the digits in decimal representation are reversed. For instance, $121$ is a palindrome, while $123$ is not.

输入格式

The first line of the input gives the number of test cases, $T$. $T$ lines follow.

Each line represents a test case and contains a single integer $A$.

输出格式

For each test case, output one line containing Case #$x$: $y$, where $x$ is the test case number (starting from $1$) and $y$ is the number of factors of $A$ which are palindromes.

4
6
10
144
242

Case #1: 4
Case #2: 3
Case #3: 7
Case #4: 6

提示

In the first test case, $A$ has $4$ factors which are palindromes: $1$, $2$, $3$, and $6$.

In the second test case, $A$ has $3$ factors which are palindromes: $1$, $2$, and $5$.

In the third test case, $A$ has $7$ factors which are palindromes: $1$, $2$, $3$, $4$, $6$, $8$, and $9$.

In the fourth test case, $A$ has $6$ factors which are palindromes: $1$, $2$, $11$, $22$, $121$, and $242$.

Limits

$1 \le T \le 100$.

Test Set $1$

$1 \le A \le 10^3$.

Test Set $2$

$1 \le A \le 10^{10}$.