{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"Your friend is a biologist. He has just sequenced a DNA and wants to know about contribution of different genes in that DNA. Both Gene and DNA can be represented by a sequence of letters or strings. Given the sequence of a DNA **D** and a Gene **G**; your friend uses following method to calculate the contribution.\n\n1. Generate a list **P** of proper non-empty prefixes of **G** and another **S** of proper non-empty suffixes of **G** [1]. Additionally let the **L** is list of all strings that is concatenation of a prefix and a suffix. So if **G \u003d ACCT** then **P \u003d A, AC, ACC** and **S \u003d T, CT, CCT** and **L \u003d AT, ACT, ACCT, ACT, ACCT, ACCCT, ACCT, ACCCT, ACCCCT**. If **|G| \u003d n** then it is obvious that size of **L** is **(n - 1)\u003csup\u003e2\u003c/sup\u003e**.\n2. For each element of **L**, count number of times it occurs as substring in **D**. Contribution of Gene **G** in DNA **D** is total of these values. For example if **D \u003d ACTACCTACCCCT** then:\n\n\n\n| Gene | Frequency |\n| --------- | --------- |\n| AT | 0 |\n| ACT | 1 |\n| ACCT | 1 |\n| ACT | 1 |\n| ACCT | 1 |\n| ACCCT | 0 |\n| ACCT | 1 |\n| ACCCT | 0 |\n| ACCCCT | 1 |\n| **Total** | **6** |\n\n\n\nAs this process is very clumsy he wants to automate this process. As he is not a programmer, he needs your help. He will be very grateful if you kindly write him a program which will read the sequence of the DNA and the Gene, and will calculate contribution of the Gene in the DNA."}},{"title":"Input","value":{"format":"MD","content":"Input starts with an integer **T (\u0026le; 20)**, denoting the number of test cases.\n\nEach case contains two lines. The first line contains a string denoting the sequence of DNA, and the second line contains another string denoting the Gene. The length of each string is less than **50000** and consists of only **A, C, T** and **G**."}},{"title":"Output","value":{"format":"MD","content":"For each case, print the case number and the contribution, as described above."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\nACTACCTACCCCT\nACCT\nAAA\nAAAA\nAAAA\nAAA\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 6\nCase 2: 4\nCase 3: 8\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"MD","content":"1. Proper prefix (suffix) of a string **S** is a prefix (suffix) of length smaller than **|S|**. Here **|S|** denotes length of **S**.\n2. Dataset is huge, use faster I/O methods."}}]}