P16874 [GKS 2022 #B] Palindromic Factors

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.

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}$.