#include <stdio.h>
#include <string.h>
long long reverseNumber(long long x) {
    static char buf[32];
    sprintf(buf, "%lld", x);
    
    long long y = 0;
    for (int i = strlen(buf) - 1; i >= 0; i--)
        y = y * 10 + buf[i] - '0';
    return y;
}
long long f(long long n) {
    if (n < 10)
        return n;
    long long half = 1;
    while (half * half <= n)	
        half *= 10;
    if (n % half == 0)	// 1000 -> 999, 10000 -> 9999
        return 1 + f(n - 1);
    else {				
        long long v = reverseNumber(n - n%half + 1);
        if (v != n - n%half + 1)	// 123654 -> 100321, subtract & reverse
            return n%half + f(v);
        else						// 19 -> 11, but 11 is palindrome, without reverse -> 10
            return n%half + f(v-1);
    }
}
int main() {
    int testcase, cases = 0;
    long long n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%lld", &n);
        printf("Case #%d: %lld\n", ++cases, f(n));
    }
    return 0;
}

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int main() {
    int testcase, cases = 0;
    int N, M, K;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &N, &M, &K);
        
        vector<int> B, W;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                int adj = 0;
                for (int k = 0; k < 4; k++) {
                    int x = i + dx[k], y = j + dy[k];
                    if (x >= 0 && y >= 0 && x < N && y < M)
                        adj++;
                }
                if ((i+j) %2 == 0)
                    B.push_back(adj), W.push_back(0);
                else
                    B.push_back(0), W.push_back(adj);
            }
        }
        
        sort(B.begin(), B.end());
        sort(W.begin(), W.end());
        
        int cost1 = 0, cost2 = 0, ret = -1;
        for (int i = 0; i < K; i++) {
            cost1 += B[i];
            cost2 += W[i];
        }
        ret = min(cost1, cost2);
        printf("Case #%d: %d\n", ++cases, ret);
    }
    return 0;
}

#include <stdio.h>
#include <set>
#include <algorithm>
using namespace std;
const int MAXN = 524288;
int N, pass[MAXN];
struct Node {
    long long arrive_time, v;
    int id;
    Node(long long a = 0, int b = 0, long long c = 0):
        arrive_time(a), id(b), v(c) {}
    bool operator<(const Node &a) const {
        if (arrive_time != a.arrive_time)
            return arrive_time < a.arrive_time;
        return v < a.v;
    }
};
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &N);
        
        set<Node> pQ;
        int id = 0;
        long long D, H, M;
        for (int i = 0; i < N; i++) {
            scanf("%lld %lld %lld", &D, &H, &M);
            for (int j = 0; j < H; j++) {
                long long arrive_time = (360 - D) * (M + j);
                pQ.insert(Node(arrive_time, id, M + j));
                pass[id] = 0, id++;
            }
        }
        
        int ret = id, encounter = id;
        
        for (; encounter <= 2 * id; ) {
            Node u = *pQ.begin(); 			// extract minimum
            
            ret = min(ret, encounter);
            
            if (pass[u.id])
                encounter++;
            else
                encounter--;
            pass[u.id] = 1;
            
            pQ.erase(pQ.begin());
            pQ.insert(Node(u.arrive_time + u.v * 360, u.id, u.v));
        }
        
        printf("Case #%d: %d\n", ++cases, ret);
    }
    return 0;
}

// NOTES: has error test data, there are some characters which aren't lowercase letters.
// FUCK
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <map>
#include <algorithm>
#include <assert.h>
#include <assert.h>
#pragma comment( linker, "/STACK:1024000000,1024000000")
using namespace std;
const int MAXCHAR = 26;
const int MAXNODE = 1048576;
class ACmachine {
public:
    struct Node {
        Node *next[MAXCHAR], *fail;
        int cnt, val, id, nid;
        void init() {
            fail = NULL;
            cnt = val = 0;
            nid = id = -1;
            memset(next, 0, sizeof(next));
        }
    } nodes[MAXNODE];
    Node *root;
    int size;
    vector<int> fg[MAXNODE];
    Node* getNode() {
        Node *p = &nodes[size++];
        p->init(), p->nid = size-1;
        assert(size < MAXNODE);
        fg[p->nid].clear();
        return p;
    }
    void init() {
        size = 0;
        root = getNode();
    }
    int toIndex(char c) {
    	assert(c - 'a' >= 0 && c - 'a' < MAXCHAR);
        return c - 'a';
    }
    void dfs(Node *p, Node *q) {
        for (int i = 0; i < MAXCHAR; i++) {
            if (q->next[i]) {
                Node *u = p->next[i], *v = q->next[i];
                if (u == NULL)
                    p->next[i] = getNode(), u = p->next[i];
                u->cnt |= v->cnt;
                dfs(u, v);
            }
        }
    }
    void merge(const ACmachine &other) {
        dfs(root, other.root);
    }
    void insert(const char str[], int sid) {
        Node *p = root;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            if (p->next[idx] == NULL)
                p->next[idx] = getNode();
            p = p->next[idx];
        }
        p->cnt = 1;
        if (sid >= 0)	p->id = sid;
    }
    int find(const char str[]) {
        Node *p = root;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            if (p->next[idx] == NULL)
                p->next[idx] = getNode();
            p = p->next[idx];
        }
        return p->cnt;
    }
    void build() { // AC automation    
        queue<Node*> Q;
        Node *u, *p;
        Q.push(root), root->fail = NULL;
        while (!Q.empty()) {
            u = Q.front(), Q.pop();
            if (u != root) {
            	assert(u->fail != NULL);
            	assert(u->nid != u->fail->nid);
            	fg[u->nid].push_back(u->fail->nid);
            	fg[u->fail->nid].push_back(u->nid);
            }
            for (int i = 0; i < MAXCHAR; i++) {
                if (u->next[i] == NULL)
                    continue;
                Q.push(u->next[i]);
                p = u->fail;
                while (p != NULL && p->next[i] == NULL)
                    p = p->fail;
                if (p == NULL || p->next[i] == NULL)
                    u->next[i]->fail = root;
                else
                    u->next[i]->fail = p->next[i];
                u->next[i]->val = u->next[i]->fail->val + u->next[i]->cnt;
                u->next[i]->id = u->next[i]->fail->id | u->next[i]->id;
            }
        }
    }
    int query(const char str[]) {
        Node *u = root, *p;
        int matched = 0;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            while (u->next[idx] == NULL && u != root)
                u = u->fail;
            u = u->next[idx];
            u = (u == NULL) ? root : u;
            p = u;
            matched += p->val;
        }
        return matched;
    }
    void free() {
        return ;
        // owner memory pool version
        queue<Node*> Q;
        Q.push(root);
        Node *u;
        while (!Q.empty()) {
            u = Q.front(), Q.pop();
            for (int i = 0; i < MAXCHAR; i++) {
                if (u->next[i] != NULL) {
                    Q.push(u->next[i]);
                }
            }
            delete u;
        }
    }
};
const int MAXN = 1048576;
class SegmentTree {
public:
    struct Node {
        long long mx;
        pair<int, long long> label;
        void init() {
            mx = -1LL<<60;
            label = make_pair(0, 0);
        }
    } nodes[MAXN];
    void pushDown(int k, int l, int r) {
        int mid = (l + r)/2;
        if (nodes[k].label.first) {
            maxUpdate(k<<1, l, mid, nodes[k].label.second);
            maxUpdate(k<<1|1, mid+1, r, nodes[k].label.second);
            nodes[k].label = make_pair(0, 0); // cancel
        }
    }
    void pushUp(int k) {
        nodes[k].mx = max(nodes[k<<1].mx, nodes[k<<1|1].mx);
    }
    void build(int k, int l, int r) { 
        nodes[k].init();
        if (l == r) {
            nodes[k].mx = 0;
            return ;
        }
        int mid = (l + r)/2;
        build(k<<1, l, mid);
        build(k<<1|1, mid+1, r);
        pushUp(k);
    } 
    // operator, assign > add
    void maxUpdate(int k, int l, int r, long long val) {
        if (nodes[k].label.first)
            val = max(val, nodes[k].label.second);
        nodes[k].label = make_pair(1, val);
        nodes[k].mx = max(nodes[k].mx, val);
    }
    void assign(int k, int l, int r, int x, int y, int val) {
        if (x <= l && r <= y) {
            maxUpdate(k, l, r, val);
            return;
        }
        pushDown(k, l, r);
        int mid = (l + r)/2;
        if (x <= mid)
            assign(k<<1, l, mid, x, y, val);
        if (y > mid)
            assign(k<<1|1, mid+1, r, x, y, val);
        pushUp(k);
    }
    // query 
    long long r_mx;
    void qinit() {
        r_mx = -1LL<<60;
    }
    void query(int k, int l, int r, int x, int y) {
        if (x <= l && r <= y) {
            r_mx = max(r_mx, nodes[k].mx);
            return ;
        }
        pushDown(k, l, r);
        int mid = (l + r)/2;
        if (x <= mid)
            query(k<<1, l, mid, x, y);
        if (y > mid)
            query(k<<1|1, mid+1, r, x, y);
    }
};
ACmachine ac;
SegmentTree tree;
vector<string> words;
vector<int> wvals;
char s[1048576];
int bPos[MAXN], ePos[MAXN], inIdx;
void prepare(int u, int p) {
    bPos[u] = ++inIdx;
    for (int i = 0; i < ac.fg[u].size(); i++) {
        if (ac.fg[u][i] == p)	continue;
        prepare(ac.fg[u][i], u);
    }
    ePos[u] = inIdx;
} 
void solve() {
    for (int i = 0; i < ac.size; i++)
        bPos[i] = ePos[i] = 0;
    inIdx = 0;
    for (int i = 0; i < ac.size; i++) {
        if (bPos[i] == 0) {
            prepare(i, -1); // interval [1, inIdx]
        }
    }
            
    assert(inIdx < MAXN/2);
    tree.build(1, 1, inIdx);
    
    long long ret = 0;
    for (int i = 0; i < words.size(); i++) {
        ACmachine::Node *u = ac.root;
        int idx;
        long long dpval = 0;
        for (int j = 0; j < words[i].length(); j++) {
            idx = ac.toIndex(words[i][j]);
            while (u->next[idx] == NULL && u != ac.root)
                u = u->fail;
            u = u->next[idx];
            u = (u == NULL) ? ac.root : u;
            
            tree.qinit();
            tree.query(1, 1, inIdx, bPos[u->nid], bPos[u->nid]);
            dpval = max(dpval, tree.r_mx);
        }
        dpval += wvals[i];
        tree.assign(1, 1, inIdx, bPos[u->nid], ePos[u->nid], dpval);
        ret = max(ret, dpval);
    }
    printf("%lld\n", ret);
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int testcase, cases = 0;
    int N, val;
    scanf("%d", &testcase);
    while (testcase--) {
    	scanf("%d", &N);
    	    	
       	ac.init();
       	words.clear(), wvals.clear();
       	for (int i = 0; i < N; i++) {
       		scanf("%s %d", s, &val);
       		ac.insert(s, i);
       		words.push_back(s), wvals.push_back(val);
       	}
       	
       	ac.build();
       	
       	printf("Case #%d: ", ++cases);
       	solve(); 
       	
        ac.free();
    }
    return 0;
}
/*
999
4
abbaaa 49
bba 41
ba 19
bbba 20
8
abbaaa 49
bba 41
ba 19
bbba 20
abbbabaaa 21
b 47
ababba 26
a 0
3
abaab 35
ab 9
abaabaaabbabababaaab 35
8
aabbbbbababbaaaab 14
abaabbaaaaaabbaabbba 13
babaaababaaaaabababa 17
abaab 35
ab 9
abaabaaabbabababaaab 35
bbbaaa 31
aabab 34
32
aa 19
bababbabbbaabaaaab 40
aabbbaaaaaa 48
ababaaabbabbbaabbb 38
a 42
bbbbbaabbbaa 10
baabbbababaab 41
aabbabbabba 28
baaab 3
aaaaaaaaa 15
bbbabbababaaabab 16
aab 18
baaab 2
abbbab 2
bababa 4
bbabbbbbaabbaaaababb 35
bbbaabba 34
bbbb 24
bbbb 17
babbbabbababababaa 9
ababaaaa 38
bbbb 3
bba 31
aabaabaaa 34
aabbbbbaababaa 41
aabbbaabbbabaababbbb 45
abbbaabbababab 37
ababbaabb 3
bbabbbbbaba 8
a 10
babbabaabbbbab 34
bbababaaaaaaaaa 5
 */

// sweep line algorithm
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int LCM = 2520; // gcd(1, 2, 3, ..., 10) = 2520, /vx, /vy, vx, vy <= 10
int W, H;
pair<int, int> getTime(int sx, int sy, int vx, int vy) {
    int enter = 0, leave = INF;
    if (vx == 0) {
        if (sx <= 0 || sx >= W)
            leave = 0;
    } else if (vx < 0) {
        enter = max(enter, (sx - W) * LCM / (-vx));
        leave = min(leave, (sx - 0) * LCM / (-vx));
    } else {
        enter = max(enter, (0 - sx) * LCM / (vx));
        leave = min(leave, (W - sx) * LCM / (vx));
    }
    if (vy == 0) {
        if (sy <= 0 || sy >= H)
            leave = 0; 
    } else if (vy < 0) {
        enter = max(enter, (sy - H) * LCM / (-vy));
        leave = min(leave, (sy - 0) * LCM / (-vy));
    } else {
        enter = max(enter, (0 - sy) * LCM / (vy));
        leave = min(leave, (H - sy) * LCM / (vy));
    }
    return make_pair(enter, leave);
}
int main() {
    int testcase, N;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &W, &H);
        scanf("%d", &N);
        
        vector< pair<int, int> > D;
        for (int i = 0; i < N; i++) {
            int sx, sy, vx, vy;
            scanf("%d %d %d %d", &sx, &sy, &vx, &vy);
            pair<int, int> t = getTime(sx, sy, vx, vy);
            if (t.first < t.second) {
                D.push_back(make_pair(t.first, 1));
                D.push_back(make_pair(t.second, -1));
            }
        }
        
        sort(D.begin(), D.end());
        int ret = 0;
        for (int i = 0, s = 0; i < D.size(); i++) {
            s += D[i].second;
            ret = max(ret, s);
        }
        printf("%d\n", ret);
    }
    return 0;
}

// Euler characteristic, V - E + F = 2
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <map>
#include <assert.h>
#include <vector>
#include <string.h>
using namespace std;
#define eps 1e-8
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}	
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
    bool operator==(const Pt &a) const {
    	return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
    }
    bool operator!=(const Pt &a) const {
    	return !(a == *this);
    }
    bool operator<(const Pt &a) const {
        if (fabs(x - a.x) > eps)
            return x < a.x;
        if (fabs(y - a.y) > eps)
            return y < a.y;
        return false;
    }
    double length() {
        return hypot(x, y);
    }
    void read() {
        scanf("%lf %lf", &x, &y);
    }
};
const double pi = acos(-1);
int cmpZero(double v) {
    if (fabs(v) > eps) return v > 0 ? 1 : -1;
    return 0;
}
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
struct Seg {
    Pt s, e;
    int label;
    Seg(Pt a = Pt(), Pt b = Pt(), int l=0): s(a), e(b), label(l) {
    }
    bool operator!=(const Seg &other) const {
        return !((s == other.s && e == other.e) || (e == other.s && s == other.e));
    }
};
int intersection(Pt as, Pt at, Pt bs, Pt bt) {
    if (cmpZero(cross(as, at, bs) * cross(as, at, bt)) < 0 &&
        cmpZero(cross(bs, bt, as) * cross(bs, bt, at)) < 0)
        return 1;
    return 0;
}
Pt getIntersect(Seg a, Seg b) {
    Pt u = a.s - b.s;
    double t = cross2(b.e - b.s, u)/cross2(a.e - a.s, b.e - b.s);
    return a.s + (a.e - a.s) * t;
}
double getAngle(Pt va, Pt vb) { // segment, not vector
    return acos(dot(va, vb) / va.length() / vb.length());
}
Pt rotateRadian(Pt a, double radian) {
    double x, y;
    x = a.x * cos(radian) - a.y * sin(radian);
    y = a.x * sin(radian) + a.y * cos(radian);
    return Pt(x, y);
}
int inPolygon(vector<Pt> &p, Pt q) {
    int i, j, cnt = 0;
    int n = p.size();
    for(i = 0, j = n-1; i < n; j = i++) {
        if(onSeg(p[i], p[j], q))
            return 1;
        if(p[i].y > q.y != p[j].y > q.y &&
        q.x < (p[j].x-p[i].x)*(q.y-p[i].y)/(p[j].y-p[i].y) + p[i].x)
        cnt++;
    }
    return cnt&1;
}
double polygonArea(vector<Pt> &p) {
    double area = 0;
    int n = p.size();
    for(int i = 0; i < n;i++)
        area += p[i].x * p[(i+1)%n].y - p[i].y * p[(i+1)%n].x;
    return fabs(area) /2;
}
Pt projectLine(Pt as, Pt ae, Pt p) {
    double a, b, c, v;
    a = as.y - ae.y, b = ae.x - as.x;
    c = - (a * as.x + b * as.y);
    v = a * p.x + b * p.y + c;
    return Pt(p.x - v*a / (a*a+b*b), p.y - v*b/ (a*a+b*b));
}
// maybe collinear !!!!!!!!
int main() {
    const int MAXN = 305;
    int n, cases = 0;
    Pt D[MAXN];
    while (scanf("%d", &n) == 1 && n) {		
        int V = 0, E = 0; 
        vector<Pt> SV;
        
        for (int i = 0; i < n; i++)
            D[i].read(), SV.push_back(D[i]);
        for (int i = 0; i+1 < n; i++) {
            for (int j = i+1; j+1 < n; j++) {
                if (intersection(D[i], D[i+1], D[j], D[j+1])) {
                    Pt p = getIntersect(Seg(D[i], D[i+1]), Seg(D[j], D[j+1]));
                    SV.push_back(p);
                }
            }
        }
        
        sort(SV.begin(), SV.end());
        SV.resize(unique(SV.begin(), SV.end()) - SV.begin());
        V = SV.size(), E = n - 1;
        for (int i = 0; i < SV.size(); i++) {
            for (int j = 0; j+1 < n; j++) {
                if (onSeg(D[j], D[j+1], SV[i]) && SV[i] != D[j] && SV[i] != D[j+1])
                    E++;
            }
        }
//		printf("%d %d\n", E, V);
        int ret = E - V + 2; // V - E + F = 2, F = E - V + 2
        printf("Case %d: There are %d pieces.\n", ++cases, ret);
    }
    return 0;
}
/*
7 
1 1 1 5 2 1 2 5 5 1 3 5 1 1 
0
*/