12447번 - ワイルドカード (Small) 다국어

多くのオペレーティングシステムでは、ファイル名を指定するとき、「*」（アスタリスク）を任意の文字列（空文字列を含む）にマッチするワイルドカードとして利用できる。

ワイルドカードは複数のファイルをまとめて指定するときによく使われるが、単一のファイルをより楽に指定する目的にも使うことができる。たとえば、"pascalisamazing" というファイルを指定するとき、"pascal*" というパターンにマッチするファイルが他になければ、このパターンによって "pascalisamazing" を指定することができる。そして、"pascal*" は"pascalisamazing" よりずっと短いので、楽に入力することができる。

あなたの挑戦は、二つのファイル名が与えられたとき、片方だけにマッチする最短のパターンを求めることである。

入力の一行目には、テストケース数 T が与えられる。続いて、各二行からなる T 個のテストケースが与えられる。各テストケースでは、一行目に一番目のファイルの名前 A、二行目に二番目のファイルの名前 B が与えられる。ファイル名はアルファベットの小文字のみからなる。

制約

• 1 ≤ T ≤ 100
• A と B は異なる文字列
• A と B はともに最小で1文字、最大で10文字からなる

各テストケースに対し、次のフォーマットの一行を出力せよ。

Case #X: Y

ただし X はテストケースの番号、Y は A にマッチするが B にマッチしない最短のパターンである。なお、最短のパターンが複数ある場合は、最もアスタリスクの個数が少ないパターンを出力せよ。それでもなお候補が複数ある場合は、辞書式順序で最も小さいものを出力せよ。なお、文字の比較は、ASCII コードの大小によって行うこと。