URI Online Judge | 1817

Tsing Ling Archaeologists

By Unknown BR Brazil

Timelimit: 0

The region of Tsing Ling is internationally famous for great archaeological findings. Some of these findings, like the ruins of Tsé Lung Zhao, challenge the best scientists in the world. Ingrown in the ruins were found various pairs of character sequences of unknown meanings, and that fact became the biggest Tsing Ling enigma. Each pair has a smaller and a larger sequence. Above the portal of the Tsing Ling monastery is written that the one who discovers the meaning of the sequences will have the answer to all questions of the universe.

The german archaeologist Harry Thanan Gruber thinks he discovered the enigma, but he needs your help in the problem. He thinks the solution of the Tsé Lung Zhao character enigma will provide the numbers to decipher the book of Tsin Wu, found in the same region by his mastermind, Dr. Cauchy-Schwartz, in the late nineteenth century. Acording to Herr Gruber's conjecture, the number sequence that must be used to decipher the enigma is given by the number of times that the smaller sequence occurs in the larger sequence as a subsequence.

Input

Several pairs of sequences are given. For each pair is given the number 0 ≤ m ≤ 100 of characters in the smaller or equal sequence and the number 0 ≤ n ≤ 1000 of characters in the largest sequence. In the following lines are given the two sequences, one per line, first the smaller and then the larger. Values m = n = 0 indicate the end of the dataset.

Output

For each pair of sequences, from now on called instances, you must print an identifier "Instancia h", where h is an integer number, sequential and increasing from 1. In the next line, you must print the number of times the smaller sequence occurs as a subsequence of the larger. A blank line must separate each instance output.

Sample Input Sample Output

3 10
*x2
a**x***xX2
0 0

Instancia 1
7