PROG0216 - Find the country

Looking for the hidden country in a given sentence. This hidden country is formed by consecutive letters of the sentence, where white space and characters that are not letters of the alphabet are to be ignored. When looking for the country in the sentence, no distinction should be made between uppercase and lowercase letters. On the basis of the country and the sentence in which this country is hidden, you have to reveal at what position in the sentence the country can be found.

Input

The first line of the input contains a number indicating how many country-sentence pairs are to follow. Then you always get two lines with country-sentence pairs: first the country, then the sentence. Each on a separate line. You may assume that the country occurs at least once in the sentence.

Output

You give the position in the sentence where the country can be found. This position is given as an index in the sentence where the first letter of the country is, where counting indices starts from 0.

Example

Input:

2
Mali
Panama lies in Central America.
Poland
The criminal was arrested by Interpol and the local police. 

Output:

4
34

Linda Kelchtermans moet op zoek gaan naar het verborgen land in een gegeven zin. Dit verborgen land wordt gevormd door opeenvolgende letters van de zin, waarbij witruimte en karakters die geen letter uit het alfabet vormen moeten genegeerd worden. Bij het vinden van het land in de zin moet geen onderscheid gemaakt worden tussen hoofdletters en kleine letters. Linda blijkt er echter maar niet in te slagen om het juiste land te vinden, en ze vraagt je om haar een tip geven. Op basis van het land en de zin waarin dit land verborgen zit, moet je haar zeggen op welke positie in de zin het land kan gevonden worden.

Invoer

De eerste regel van de invoer bevat een getal dat aangeeft hoeveel land-zin paren er gaan volgen. Vervolgens krijg je steeds op twee regels de land-zin paren: eerst het land, dan de zin. Elk op een afzonderlijke regel. Je mag ervan uitgaan dat het land steeds minstens één keer in de zin voorkomt.

Uitvoer

Je geeft de positie in de zin terug waar het land kan gevonden worden. Deze positie wordt gegeven als index in de zin waar de eerste letter van het land staat, waarbij men de indices begint te tellen vanaf 0.

Voorbeeld

Invoer:

2
Mali
Panama ligt in Centraal-Amerika.
Polen
Elke keuken heeft wel meerdere pol- en soeplepels.

Uitvoer:

4
31

Added by:Peter Dawyndt
Date:2012-02-08
Time limit:10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:
Resource:None

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.