<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

537. Divisibility
Time limit per test: 1.5 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

Inspired by Stephen Graham, the King of Berland started to study algorithms on strings. He was working days and nights, having a feeling that the full potential in this area is still to be unlocked. And he was right!

One day, all the sudden, he made a huge breakthrough by discovering the fact that strings can be magically transformed into integer numbers. It was so simple! You just have to map different letters to different digits and be careful enough not to introduce any leading zeroes.

Here is what he wrote in his textbook about the string 'lalala':
it can be transformed to an 282828 by mapping 'l' to 2, and 'a' to 8
it can also be transformed to 909090 by mapping 'l' to 9, and 'a' to 0
a couple of examples of invalid transformations are 050505 (the resulting number has a leading zero), 333333 (different letters are mapped to the same digit), 123456 (no mapping to the original letters at all)


But then things started to become more interesting. Obviously, it was known from very beginning that a single string can potentially be mapped to a variety of different integer numbers. But the King couldn't even imagine that all numbers produced by the same string pattern might have common properties!

For example, every single number that can be produced from string 'lalala' is always divisible by 259, irrespective of the letter-to-digit mapping you choose. Fascinating!

So the King ended up with the following problem. For any given string, he wanted to come up with an algorithm to calculate the set of its divisors. A number is called a divisor of the given string if all positive integers, that could possibly be produced from the given string, are divisible by it.

As usual, the King desperately wants you to help him, so stop thinking and start acting!

Input
Input consists of multiple test cases. The first line of input contains an integer number n (1 ≤ n ≤ 100) — the number of test cases.

Each of the next n lines contains a string pattern to be processed. Each pattern consists of lowercase Latin letters. Its length will always be between 1 and 14 characters, and the number of different characters in the pattern will never exceed 10 to ensure correct mapping to digits 0-9.

Output
For every test case print a line with the corresponding test case number and the calculated list of divisors. Output positive divisors in an increasing order, separating them with a single space. Format your output according to the example given in the sample test case.

Example(s)
sample input
sample output
5
cat
bbb
ololo
lala
icpcicpc
Case 1: 1
Case 2: 1 3 37 111
Case 3: 1
Case 4: 1 101
Case 5: 1 73 137 10001

<|response|>
1. Abridged Problem Statement
You are given a lowercase string s of length up to 14 and containing at most 10 distinct letters. We consider all ways to map each distinct letter to a distinct digit (0-9), with the restriction that the first letter of s cannot map to 0. Each mapping phi produces an integer N(phi). Find all positive integers d such that N(phi) is divisible by d for every valid mapping phi. Output these divisors in increasing order.

2. Key Observations
- Any mapped number can be written as
    N(phi) = sum_{c in letters} mask[c] * phi(c)
  where mask[c] = sum_{i: s[i]=c} 10^{(n-1-i)}.
- We compute g = gcd over all valid N(phi) in two stages:
  (a) Backtracking enumerates up to 200 valid letter-to-digit assignments and folds each resulting number into g directly.
  (b) For every pair of distinct letters x and y with nearby digit values (|x_val - y_val| <= 1), the swap difference equals (mask_x + mask_y) * (x_val - y_val). Folding these differences into g ensures g converges to the true GCD.
- Once g is known, factorize it by trial division and enumerate all divisors.

3. Full Solution Approach
1. Read s, compute mask[c] for each distinct letter by walking right-to-left.
2. Run backtracking that assigns distinct digits respecting the no-leading-zero constraint, accumulating gcd of all produced numbers; stop after 200 valid assignments.
3. For every ordered pair of distinct letters (x, y) and every pair of nearby digit values (x_val, y_val) (|x_val - y_val| <= 1, not violating the no-leading-zero rule), fold the value (mask_x + mask_y) * |x_val - y_val| into g.
4. Factorize g by trial division up to sqrt(g).
5. Generate all divisors from the prime factorization using the standard multiply-out method.
6. Sort and print them.

4. C++ Implementation with Comments
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

string s;

void read() { cin >> s; }

void backtracking(
    vector<int>& mapping, int64_t& g, int digit_mask, int pos, int64_t curr,
    int& steps
) {
    if(g == 1 || steps <= 0) {
        return;
    }

    if(pos == s.size()) {
        g = gcd(g, curr);
        steps--;
        return;
    }

    int c = s[pos] - 'a';
    if(mapping[c] != -1) {
        backtracking(
            mapping, g, digit_mask, pos + 1, curr * 10 + mapping[c], steps
        );
    } else {
        for(int d = (pos == 0); d < 10; d++) {
            if(digit_mask & (1 << d)) {
                continue;
            }
            mapping[c] = d;
            backtracking(
                mapping, g, digit_mask | (1 << d), pos + 1, curr * 10 + d, steps
            );
            mapping[c] = -1;
        }
    }
}

void solve() {
    // A common divisor must divide every number the pattern can produce. We
    // collect a g = gcd of several producible numbers and reasonable
    // differences between them, then output all divisors of g.
    //
    // First, backtracking enumerates up to a few hundred valid letter-to-digit
    // assignments (distinct digits, no leading zero) and folds each resulting
    // number into g. Then we use the place-value mask of each letter: masks[c]
    // is the sum of powers of ten over the positions where c occurs. Swapping
    // the digits of two letters x and y keeps the value producible but changes
    // it by (mask_x + mask_y) * (y - x); the gcd is unchanged by adding such a
    // difference, so for every admissible pair of letters and nearby digit
    // values (respecting distinctness and the no-leading-zero rule) we fold
    // that difference into g as well. Finally g is fully factorised and all of
    // its divisors are generated and printed in increasing order.

    int n = s.size();
    vector<int> mapping(26, -1);
    int64_t g = 0;
    int steps = 200;
    backtracking(mapping, g, 0, 0, 0, steps);

    map<char, int64_t> masks;
    int64_t mask = 1;
    for(int i = n - 1; i >= 0; i--) {
        masks[s[i]] += mask;
        mask = mask * 10;
    }

    for(auto [xl, mask_x]: masks) {
        for(auto [yl, mask_y]: masks) {
            for(int x = 0; x < 10; x++) {
                for(int y = max(x - 1, 0); y < min(x + 2, 10); y++) {
                    if(xl == yl || x == y || (xl == s[0] && x == 0) ||
                       (yl == s[0] && y == 0) || (xl == s[0] && y == 0) ||
                       (yl == s[0] && x == 0)) {
                        continue;
                    }
                    g =
                        gcd(g, -mask_x * (int64_t)(x - y) -
                                   mask_y * (int64_t)(y - x));
                }
            }
        }
    }

    assert(g > 0);

    vector<pair<int64_t, int>> prime_divs;
    for(int64_t x = 2; x * x <= g; x++) {
        if(g % x != 0) {
            continue;
        }

        int cnt = 0;
        while(g % x == 0) {
            cnt++;
            g /= x;
        }
        prime_divs.push_back({x, cnt});
    }

    if(g > 1) {
        prime_divs.push_back({g, 1});
    }

    vector<int64_t> all_divs = {1};
    for(auto [x, cnt]: prime_divs) {
        int sz = all_divs.size();
        for(int i = 0; i < sz; i++) {
            int64_t y = all_divs[i];
            for(int j = 1; j <= cnt; j++) {
                all_divs.push_back(y * x);
                y *= x;
            }
        }
    }

    sort(all_divs.begin(), all_divs.end());
    cout << all_divs << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        cout << "Case " << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python Implementation with Comments
```python
import sys, threading
def main():
    import math
    sys.setrecursionlimit(10**7)
    T = int(sys.stdin.readline())
    for tc in range(1, T+1):
        s = sys.stdin.readline().strip()
        n = len(s)

        # Compute weight mask for each letter: sum of 10^(position)
        mask = {}
        place = 1
        # iterate from least significant digit (rightmost) back to left
        for i in range(n-1, -1, -1):
            c = s[i]
            mask[c] = mask.get(c, 0) + place
            place *= 10

        letters = list(mask.items())  # list of (char, weight)
        m = len(letters)

        # Compute G
        if m == 1:
            # Only one letter: G = mask * gcd(notes 1..9) = mask
            G = letters[0][1]
        else:
            G = 0
            # gcd over all sums mask[c]+mask[d]
            for i in range(m):
                for j in range(i+1, m):
                    wsum = letters[i][1] + letters[j][1]
                    G = math.gcd(G, wsum)

        # Now factor G to get divisors
        # For G up to ~1e14, trial division up to sqrt is feasible in Python
        # since G is special (sum of few powers of 10) and small prime count.
        fac = []
        tmp = G
        # trial divide by small primes
        f = 2
        while f*f <= tmp:
            if tmp % f == 0:
                cnt = 0
                while tmp % f == 0:
                    tmp //= f
                    cnt += 1
                fac.append((f, cnt))
            f += 1 if f==2 else 2  # skip even numbers after 2
        if tmp > 1:
            fac.append((tmp, 1))

        # Generate all divisors from prime factorization
        divisors = [1]
        for (p, cnt) in fac:
            cur = []
            # for each existing divisor d, multiply by p^e for e in [1..cnt]
            for d in divisors:
                val = d
                for _ in range(cnt):
                    val *= p
                    cur.append(val)
            divisors += cur

        divisors.sort()
        # Output
        print("Case {}: {}".format(tc, " ".join(str(d) for d in divisors)))

if __name__ == "__main__":
    main()
```
