Giải bài trực tuyến

After several years of preparing, Vietnam has been chosen to organize the IOI2023, it's such a big even with Vietnamese fans of informatics! The host country wants to invite all guests to visit N famous places (numbered 0..N-1). Of course the journey will start from the capital Hanoi (numbered 0). And after many years of developing, the travel system has been so modern that it needs only exactly N-1 highways for guests to travel to all N places from the capital. It's not only that but Ministry of Culture and Information also has an idea to paint some slogans on the highways to advertise Vietnam and the IOI competition. KTuan wants to watch the competition so he came back to Vietnam early. On the days in Hanoi, KTuan met AnhDQ (an old friend) by chance. Hearing that exciting idea, KTuan has a slogan in his mind and wants to ask AnhDQ: how many times it appears on the way from Hanoi to the places?. Please help AnhDQ answer KTuan's question!

Input

- The first line contains N.
- N-1 following lines, each line contains two number u, v and the string S, showing a highway from u to v, on which is painted the string S directed u->v.
- The last line contains KTuan's slogan.

Output

- The answer of AnhDQ.

Example

Input:
11
0 2 Welcom
0 7 VietN
2 8 nauTK
7 3 am
7 9 nauTK
2 5 eKTuan
5 4 IOIKTuanIO
7 1 IOI
5 6 IOI23
4 10 I2023
KTuanIOI

Output:
3

*** Explaination:
On the way 0-2-5-6: WelcomeKTuanIOI23
On the way 0-2-5-4-10: WelcomeKTuanIOIKTuanIOI2023

Limitations

- N ≤ 17032.
- The length of the strings ≤ 1000.
- The length of KTuan's slogan ≤ 70.

Sorry for my bad English!^_^ Please comment for a better translation ;)