25085번 - 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.

제한

• 1ドル≤T≤100$.

Test Set 1 (6점)

• 1ドル≤A≤10^3$.

Test Set 2 (9점)

• 1ドル≤A≤10^{10}$.

힌트

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ドル$.