你正計畫去歐洲旅行，但是你不知道該到哪些城市，所以你就向父母尋求建議。

你的母親說：「兒子呀！你應該去巴黎、馬德里、里斯本和倫敦，而且要按照這樣的順序去玩。」

你的父親卻說：「No,No,No, 你應該先去巴黎，然後里斯本，然後倫敦，最後才去馬德里。相信我。」

現在你陷入一個困境中了，如果你聽從父親的建議，那會傷了母親的心。如果你聽從了母親的建議，那會傷了父親的心。但是如果你不管他們的建議，更可能傷了他們 2 個人的心。

所以你決定盡可能的聽從他們 2 人的建議。所以你決定了：巴黎，里斯本，倫敦這樣順序的旅程，以滿足你的父母親。雖然這個決定使你只能到巴黎，里斯本，倫敦這 3 個城市去，而無法去馬德里。

如果你的父親建議：「倫敦–巴黎–里斯本–馬德里」這樣的旅程，那麼你將有 2 組組合：「巴黎–里斯本」及「巴黎–馬德里」來盡可能滿足你的父母。在這個情況下，你就只能去 2 個城市玩了。

你想要避免將來要面臨這樣的難題，如果他們建議的城市更多的話。所以你想要寫一個程式來幫助你。你將每個城市以一個字元來表示，這些字元包括大小寫英文字母，數字，以及空白字元。因此，你可以到 63 個城市可以去玩。但是請注意：你可能會到一個城市不止一次。

假如你以 a 代表巴黎，b 代表馬德里，c 代表里斯本，d 代表倫敦，那你母親建議的旅程順序就是：abcd，而你父親建議的則是：acdb (上面的第一個例子)

程式必須輸入父母所建議的 2 個旅程，然後回答在盡可能滿足你父母的情況下，你最多可以去多少個城市旅行。

Input

輸入含有多組測試資料。每一組測試資料 2 列，分別代表你父母所建議的 2 個旅程 (每列最多 100 個字元)。當遇到一列內容為單一 # 時，代表輸入結束。請參考 Sample Input。

Output

每組測試資料輸出在盡可能滿足你父母的情況下，你最多可以去多少個城市旅行。請參考 Sample Output。

Sample Input

abcd
acdb
abcd
dacb
#

Sample Output

Case #1: you can visit at most 3 cities.
Case #2: you can visit at most 2 cities.

給你 2 個字串，請你輸出他們的最長共同子字串 (longest common subsequence) 的長度。例如：給你以下 2 個字串：

abcdgh
aedfhr

他們的最長共同子字串為 adh，長度為 3。

Input

輸入含有多組測試資料。每一組測試資料 2 列，分別代表這 2 個字串 (最多 1000 個字元)。

Output

每組測試資料輸出他們的最長共同子字串 (longest common subsequence) 的長度。

Sample Input

a1b2c3d4e
zz1yy2xx3ww4vv
abcdgh
aedfhr
abcdefghijklmnopqrstuvwxyz
a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0p0q0r0s0t0u0v0w0x0y0z0
abcdefghijklmnzyxwvutsrqpo
opqrstuvwxyzabcdefghijklmn

Sample Output

4
3
26
14

有些人認為大象是越大隻的越聰明。為了要反證這項說法，你想要用收集到的大象資料列出一個大象數目最大的子集合，在這個子集合中，大象的體重是漸增的，而智商是漸減的。

Input

只有一組測試資料，包含了最多 1000 隻大象的體重及智商的資料。每隻大象一列，有 2 個整數 $W_i$ 及 $S_i$ (介於 1 和 10000 之間) 分別代表第 $i$ 隻大象的體重及智商。大象的編號從 1 開始。

不同的大象可能有相同的重量，相同的智商，或相同的重量及智商。

Output

第一列輸出一個整數 $n$，代表你可以找到的子集合最大的大象數目。接下來的 $n$ 列，每列有一個正整數，代表某隻大象的編號。

如果這 $n$ 個正整數是 $a_1,a_2,\ldots{},a_n$，那它應該要符合

解答可能不只一個，請輸出其中任何一個即可。

Sample Input

6008 1300
6000 2100
500 2000
1000 4000
1100 3000
6000 2000
8000 1400
6000 1200
2000 1900

Sample Output

4
4
5
9
7

把一個數字反轉並相加的方法很簡單：就是把數字反轉並加上原來的數字。假如這個和不是一個迴文（指這個數字從左到右和從右到左都相同），就一直重複這個程序。舉例說明：

195 開始的數字
591
-----
786
687
-----
1473
3741
-----
5214
4125
-----
9339 迴文出現了

在這個例子中，經過了 4 次相加後得到了迴文 9339。幾乎對所有的整數這個方法都會得到迴文，但是也有有趣的例外。196 是第 1 個用這個方法找不到迴文的數字，然而並沒有證明該迴文不存在。

現在給你一個開始的數字，你的任務就是求出經過多少次相加後，會產生哪一個迴文。對所有的測試資料，你可以假設：

1. 都會有 1 個答案。
2. 在 1000 個相加內都會得到答案。
3. 產生的迴文不會大於 4294967295。

Input

第 1 列有一個整數 $N$ ($0 < N \leq 100$)，代表以下有幾組測試資料。每筆測試資料一列，各有 1 個整數 $P$，就是開始的數字。

Output

對每一測試資料，請輸出 2 個數字：得到迴文所需的最少次數的相加，以及該迴文。

Sample Input

5
195
265
750
2
99

Sample Output

4 9339
5 45254
3 6666
1 4
6 79497

密碼翻譯 (cryptanalysis) 是指把某個人寫的密文 (cryptographic writing) 加以分解。這個程序通常會對密文訊息做統計分析。你的任務就是寫一個程式來對密文作簡單的分析。

Input

輸入的第 1 列有一個正整數 n，代表以下有多少列需要作分析的密文。

接下來的 n 列，每列含有 0 或多個字元 (可能包含空白字元)

Output

每列包含一個大寫字元 (A ~ Z) 和一個正整數。這個正整數代表該字元在輸入中出現的次數。輸入中大小寫 (例如：A 及 a) 視為相同的字元。輸出時請按照字元出現的次數由大到小排列，如果有 2 個以上的字元出現次數相同的話，則按照字元的大小 (例如：A 在 H 之前) 由小到大排列。

請注意：如果某一字元未出現在輸入中，那他也不應出現在輸出中。

Sample Input

3
This is a test.
Count me 1 2 3 4 5.
Wow!!!! Is this question easy?

Sample Output

S 7
T 6
I 5
E 4
O 3
A 2
H 2
N 2
U 2
W 2
C 1
M 1
Q 1
Y 1