Description

    MatRush的好朋友XadillaX暑假在一家西班牙的公司实习，在实习过程中他碰到了一个难题：怎样计算两串文字之间的相似度呢？现在他想让聪明的你来帮他完成这项任务。

  给定一个模式串(pattern)和一个文本(text)，我们可以将它们按很多方式对齐，使得每个模式串中的字母在文本里都有一个相对应的字符。XadillaX只考虑连续的对齐方式。对于每种这样的对齐方式，我们能获得模式串和文本的相应位置上字符相同的个数。把这个个数的总和叫做该模式串和文本的相似度，如下表展示了模式串abaab和文本aababacab的相似度的计算过程：

现在XadillaX把他想求的模式串和文本都告诉你了，请你帮他计算出相似度。

Input

输入的第一行包含一个整数 T，表示测试数据的组数。 每组数据包含两行，第一行是由小写字母组成的非空模式串，第二行是由小写字母组成的非空文本串。数据保证模式串的长度不超过文本串的长度，并且文本串长度小于2000000。

Output

对于每组数据输出一行，表示给定的模式串和文本的相似度。

Sample

Input

2
abaab
abaab
abaab
aababacab

Output

5
12

Source: CEOI2011 Day0 Warmup