The Genome Database of All Space Life Returns

Extraterrestrial Life Genome Database Returns

In 2301 AD, the Department of Life Sciences of the Federal Republic of Space was studying the genome sequences of space organisms. As a result of recent research, it has become clear that the number of times a specific pattern appears in the genome sequence has a great influence on the properties of the organism.

The genome sequence of space organisms is represented by a character string consisting of uppercase letters. Researchers have decided to count how many times a particular pattern appears in a genomic sequence. However, since the genome sequence of space organisms is very long, the substrings with repetitions are compressed and stored in the database by the method described later.

Your job is to create a program that counts the number of occurrences of the string Q from the compressed genomic sequence S. However, the appearance of Q is counted as another appearance even if there is an overlapping part, as long as the start position is different. For example, ISSI appears twice in MISSISSIPPI.

The method of compressing the genome sequence is defined by the following BNF.

:: = | | () | :: ='A' |'B' |… |' Z' :: = | '0' | :: = '1' | '2' |… | '9'

Here, the integer prefixed to the character string indicates that the character string is repeated that number of times. For example, 5A stands for AAAAA and 2 (AB) stands for ABAB. If there is no parenthesis immediately after the integer, only the one character immediately after it is repeated. For example, 2AB stands for AAB. The iterations can be nested multiple times, and 2 (2 (AB) C) is the same as 2 (ABABC) and represents ABABCABABC.

Input

The input consists of up to 50 datasets. Each dataset is represented in the following format.

S Q

The first line of each dataset is the string S, which represents the compressed genomic sequence. According to the above BNF, S has a length of 1 or more and 3000 characters or less. The length of the original genome sequence from which S was expanded is 1018 or less. The second line of each dataset is the string Q to be counted. Q consists of uppercase letters and is 1 or more and 3000 characters or less in length.

The end of the input is represented by a line containing only one character,'#'.

Output

For each dataset, output how many times Q appears in the expanded string of S.

Sample Input

MI2 (2SI) 2PI ISSI 100 (100 (JAG)) JAG 1000000000000000000A AAAAA

Output for the Sample Input

2 10000 999999999999999996

Example

Input

MI2(2SI)2PI ISSI 100(100(JAG)) JAG 1000000000000000000A AAAAA

Output

2 10000 999999999999999996

inputFormat

Input

The input consists of up to 50 datasets. Each dataset is represented in the following format.

S Q

The first line of each dataset is the string S, which represents the compressed genomic sequence. According to the above BNF, S has a length of 1 or more and 3000 characters or less. The length of the original genome sequence from which S was expanded is 1018 or less. The second line of each dataset is the string Q to be counted. Q consists of uppercase letters and is 1 or more and 3000 characters or less in length.

The end of the input is represented by a line containing only one character,'#'.

outputFormat

Output

For each dataset, output how many times Q appears in the expanded string of S.

Sample Input

MI2 (2SI) 2PI ISSI 100 (100 (JAG)) JAG 1000000000000000000A AAAAA

Output for the Sample Input

2 10000 999999999999999996

Example

Input

MI2(2SI)2PI ISSI 100(100(JAG)) JAG 1000000000000000000A AAAAA

Output

2 10000 999999999999999996

样例

MI2(2SI)2PI
ISSI
100(100(JAG))
JAG
1000000000000000000A
AAAAA
#

2
10000
999999999999999996

</p>