Everyone hates ugly problems. 

You are given a positive integer. You must represent that number by sum of palindromic numbers. 

A palindromic number is a positive integer such that if you write out that integer as a string in decimal without leading zeros, the string is an palindrome. For example, 1 is a palindromic number and 10 is not.

Input

In the first line of input, there is an integer T denoting the number of test cases.

For each test case, there is only one line describing the given integer s (1≤s≤1010001≤s≤101000).

Output

For each test case, output “Case #x:” on the first line where x is the number of that test case starting from 1. Then output the number of palindromic numbers you used, n, on one line. n must be no more than 50. en output n lines, each containing one of your palindromic numbers. Their sum must be exactly s.

Sample Input

2
18
1000000000000

Sample Output

Case #1:
2
9
9
Case #2:
2
999999999999
1

Hint

9 + 9 = 18
999999999999 + 1 = 1000000000000

题意：把一个大数拆成几个回文数的和，回文数的数量小于等于50个。

题解：运用java大数来写，看代码，代码里有解释

import java.util.*;
import java.math.*;
public class Main {
	static Scanner cin = new Scanner(System.in);
	public static void main(String[] args){
		int t;
		t = cin.nextInt();
		BigInteger a = BigInteger.valueOf(0),ten=BigInteger.valueOf(20);//20是因为后面减1，如果不是20就死循环了，准确来说第一位不能是1
		BigInteger tmpa,tmpa1;
		String s,tmps,tmps1,tmps2;
		String ss[] = new String[55];//用来存每一个回文数
		int xx = 0;
		for (int i = 1; i <= t;i++) {
			xx=0;
			a = cin.nextBigInteger();//假设a为59634102长度为偶数，奇数反转时候再减1就好了，下面解释
			System.out.printf("Case #%d:\n",i);
			while(a.compareTo(ten)>=1) {
				s = a.toString();
				int len = s.length();
				tmps = s.substring(0, (len+1)/2); //5963
				tmpa = new BigInteger(tmps);
				tmpa = tmpa.subtract(BigInteger.valueOf(1));//5962
				tmps1=tmpa.toString();
				if((len&1)!=1) {//为偶数
					StringBuffer sb = new StringBuffer(tmps1);
					sb.reverse();//2695
					tmps2 = sb.toString();
					tmps=tmps1+tmps2;
					tmpa1 = new BigInteger(tmps);
					a = a.subtract(tmpa1);
					ss[xx++]=tmps;//59622695  这里只解释第一步循环
				}
				else {
					int len1=tmps1.length();
	                tmps2="";
	                for(int j = len1-2; j >= 0;j--){//再减一
	                    tmps2+=tmps1.charAt(j);
	                }
	                tmps=tmps1+tmps2;
	                tmpa1=new BigInteger(tmps);
	                a=a.subtract(tmpa1);
	                ss[xx++]=tmps;
				}
			}
			int ans = a.intValue();
			if(ans>=10) {
				ss[xx++]="9";
				ss[xx++]=String.valueOf(ans-9);
			}
			else {
				ss[xx++]=String.valueOf(ans);
			}
			System.out.println(xx);
			for (int r = 0; r < xx;r++) {
				System.out.println(ss[r]);
			}
		}
	}
}