{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003clink href\u003d\"css/light_oj.css\" rel\u003d\"stylesheet\" type\u003d\"text/css\" /\u003e\r\n\u003cp class\u003d\"MsoNormal\"\u003e\r\n\tYour 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 \u003cb\u003eD\u003c/b\u003e and a Gene \u003cb\u003eG\u003c/b\u003e; your friend uses \u003cspan style\u003d\"line-height:\r\n115%\"\u003efollowing method to calculate the contribution.\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoListParagraphCxSpFirst\" style\u003d\"text-align:justify;text-indent:-.25in\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;line-height:115%;font-family:\u0026quot;Garamond\u0026quot;,\u0026quot;serif\u0026quot;\"\u003e1.\u003cspan style\u003d\"font:7.0pt \u0026quot;Times New Roman\u0026quot;\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; \u003c/span\u003e\u003c/span\u003e\u003cspan style\u003d\"font-size:12.0pt;line-height:115%;font-family:\u0026quot;Garamond\u0026quot;,\u0026quot;serif\u0026quot;\"\u003eGenerate a list \u003cb\u003eP\u003c/b\u003e of proper non-empty prefixes of \u003cb\u003eG\u003c/b\u003e and another \u003cb\u003eS\u003c/b\u003e of proper non-empty suffixes of \u003cb\u003eG\u003c/b\u003e [1]. Additionally let the \u003cb\u003eL\u003c/b\u003e is list of all strings that is concatenation of a prefix and a suffix. So if \u003cb\u003eG \u003d ACCT\u003c/b\u003e then \u003cb\u003eP \u003d A, AC, ACC\u003c/b\u003e and \u003cb\u003eS \u003d T, CT, \u003cspan data-scayt_word\u003d\"CCT\" data-scaytid\u003d\"1\"\u003eCCT\u003c/span\u003e\u003c/b\u003e and \u003cb\u003eL \u003d AT, ACT, ACCT, ACT, ACCT, \u003cspan data-scayt_word\u003d\"ACCCT\" data-scaytid\u003d\"2\"\u003eACCCT\u003c/span\u003e, ACCT, \u003cspan data-scayt_word\u003d\"ACCCT\" data-scaytid\u003d\"3\"\u003eACCCT\u003c/span\u003e, \u003cspan data-scayt_word\u003d\"ACCCCT\" data-scaytid\u003d\"4\"\u003eACCCCT\u003c/span\u003e\u003c/b\u003e. If \u003cb\u003e|G| \u003d n\u003c/b\u003e then it is obvious that size of \u003cb\u003eL\u003c/b\u003e is \u003cb\u003e(n - 1)\u003csup\u003e2\u003c/sup\u003e\u003c/b\u003e.\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoListParagraphCxSpLast\" style\u003d\"text-align:justify;text-indent:-.25in\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;line-height:115%;font-family:\u0026quot;Garamond\u0026quot;,\u0026quot;serif\u0026quot;\"\u003e2.\u003cspan style\u003d\"font:7.0pt \u0026quot;Times New Roman\u0026quot;\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; \u003c/span\u003e\u003c/span\u003e\u003cspan style\u003d\"font-size:12.0pt;line-height:115%;font-family:\u0026quot;Garamond\u0026quot;,\u0026quot;serif\u0026quot;\"\u003eFor each element of \u003cb\u003eL\u003c/b\u003e, count number of times it occurs as \u003cspan data-scayt_word\u003d\"substring\" data-scaytid\u003d\"5\"\u003esubstring\u003c/span\u003e in \u003cb\u003eD\u003c/b\u003e. Contribution of Gene \u003cb\u003eG\u003c/b\u003e in DNA \u003cb\u003eD\u003c/b\u003e is total of these values. For example if \u003cb\u003eD \u003d \u003cspan data-scayt_word\u003d\"ACTACCTACCCCT\" data-scaytid\u003d\"6\"\u003eACTACCTACCCCT\u003c/span\u003e\u003c/b\u003e then\u003c/span\u003e\u003c/p\u003e\r\n\u003cdiv align\u003d\"center\"\u003e\r\n\t\u003ctable border\u003d\"1\" cellpadding\u003d\"0\" cellspacing\u003d\"0\" class\u003d\"MsoTableGrid\" style\u003d\"margin-left:203.4pt;border-collapse:collapse;border:none\"\u003e\r\n\t\t\u003ctbody\u003e\r\n\t\t\t\u003ctr\u003e\r\n\t\t\t\t\u003ctd style\u003d\"width:56.8pt;border:solid black 1.0pt;\r\n padding:0in 5.4pt 0in 5.4pt\" valign\u003d\"top\" width\u003d\"76\"\u003e\r\n\t\t\t\t\t\u003cp align\u003d\"center\" class\u003d\"MsoNormal\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\r\n text-align:center\"\u003e\r\n\t\t\t\t\t\tAT\u003c/p\u003e\r\n\t\t\t\t\u003c/td\u003e\r\n\t\t\t\t\u003ctd style\u003d\"width:24.2pt;border:solid black 1.0pt;\r\n border-left:none;padding:0in 5.4pt 0in 5.4pt\" valign\u003d\"top\" width\u003d\"32\"\u003e\r\n\t\t\t\t\t\u003cp align\u003d\"center\" class\u003d\"MsoNormal\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\r\n text-align:center\"\u003e\r\n\t\t\t\t\t\t0\u003c/p\u003e\r\n\t\t\t\t\u003c/td\u003e\r\n\t\t\t\u003c/tr\u003e\r\n\t\t\t\u003ctr\u003e\r\n\t\t\t\t\u003ctd style\u003d\"width:56.8pt;border:solid black 1.0pt;\r\n border-top:none;padding:0in 5.4pt 0in 5.4pt\" valign\u003d\"top\" width\u003d\"76\"\u003e\r\n\t\t\t\t\t\u003cp align\u003d\"center\" class\u003d\"MsoNormal\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\r\n text-align:center\"\u003e\r\n\t\t\t\t\t\tACT\u003c/p\u003e\r\n\t\t\t\t\u003c/td\u003e\r\n\t\t\t\t\u003ctd style\u003d\"width:24.2pt;border-top:none;border-left:none;\r\n border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;padding:0in 5.4pt 0in 5.4pt\" valign\u003d\"top\" width\u003d\"32\"\u003e\r\n\t\t\t\t\t\u003cp align\u003d\"center\" class\u003d\"MsoNormal\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\r\n text-align:center\"\u003e\r\n\t\t\t\t\t\t1\u003c/p\u003e\r\n\t\t\t\t\u003c/td\u003e\r\n\t\t\t\u003c/tr\u003e\r\n\t\t\t\u003ctr\u003e\r\n\t\t\t\t\u003ctd style\u003d\"width:56.8pt;border:solid black 1.0pt;\r\n border-top:none;padding:0in 5.4pt 0in 5.4pt\" valign\u003d\"top\" width\u003d\"76\"\u003e\r\n\t\t\t\t\t\u003cp align\u003d\"center\" class\u003d\"MsoNormal\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\r\n text-align:center\"\u003e\r\n\t\t\t\t\t\tACCT\u003c/p\u003e\r\n\t\t\t\t\u003c/td\u003e\r\n\t\t\t\t\u003ctd style\u003d\"width:24.2pt;border-top:none;border-left:none;\r\n border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;padding:0in 5.4pt 0in 5.4pt\" valign\u003d\"top\" width\u003d\"32\"\u003e\r\n\t\t\t\t\t\u003cp align\u003d\"center\" class\u003d\"MsoNormal\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\r\n text-align:center\"\u003e\r\n\t\t\t\t\t\t1\u003c/p\u003e\r\n\t\t\t\t\u003c/td\u003e\r\n\t\t\t\u003c/tr\u003e\r\n\t\t\t\u003ctr\u003e\r\n\t\t\t\t\u003ctd style\u003d\"width:56.8pt;border:solid black 1.0pt;\r\n border-top:none;padding:0in 5.4pt 0in 5.4pt\" valign\u003d\"top\" width\u003d\"76\"\u003e\r\n\t\t\t\t\t\u003cp align\u003d\"center\" class\u003d\"MsoNormal\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\r\n text-align:center\"\u003e\r\n\t\t\t\t\t\tACT\u003c/p\u003e\r\n\t\t\t\t\u003c/td\u003e\r\n\t\t\t\t\u003ctd style\u003d\"width:24.2pt;border-top:none;border-left:none;\r\n border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;padding:0in 5.4pt 0in 5.4pt\" valign\u003d\"top\" width\u003d\"32\"\u003e\r\n\t\t\t\t\t\u003cp align\u003d\"center\" class\u003d\"MsoNormal\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\r\n text-align:center\"\u003e\r\n\t\t\t\t\t\t1\u003c/p\u003e\r\n\t\t\t\t\u003c/td\u003e\r\n\t\t\t\u003c/tr\u003e\r\n\t\t\t\u003ctr\u003e\r\n\t\t\t\t\u003ctd style\u003d\"width:56.8pt;border:solid black 1.0pt;\r\n border-top:none;padding:0in 5.4pt 0in 5.4pt\" valign\u003d\"top\" width\u003d\"76\"\u003e\r\n\t\t\t\t\t\u003cp align\u003d\"center\" class\u003d\"MsoNormal\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\r\n text-align:center\"\u003e\r\n\t\t\t\t\t\tACCT\u003c/p\u003e\r\n\t\t\t\t\u003c/td\u003e\r\n\t\t\t\t\u003ctd style\u003d\"width:24.2pt;border-top:none;border-left:none;\r\n border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;padding:0in 5.4pt 0in 5.4pt\" valign\u003d\"top\" width\u003d\"32\"\u003e\r\n\t\t\t\t\t\u003cp align\u003d\"center\" class\u003d\"MsoNormal\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\r\n text-align:center\"\u003e\r\n\t\t\t\t\t\t1\u003c/p\u003e\r\n\t\t\t\t\u003c/td\u003e\r\n\t\t\t\u003c/tr\u003e\r\n\t\t\t\u003ctr\u003e\r\n\t\t\t\t\u003ctd style\u003d\"width:56.8pt;border:solid black 1.0pt;\r\n border-top:none;padding:0in 5.4pt 0in 5.4pt\" valign\u003d\"top\" width\u003d\"76\"\u003e\r\n\t\t\t\t\t\u003cp align\u003d\"center\" class\u003d\"MsoNormal\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\r\n text-align:center\"\u003e\r\n\t\t\t\t\t\t\u003cspan data-scayt_word\u003d\"ACCCT\" data-scaytid\u003d\"7\"\u003eACCCT\u003c/span\u003e\u003c/p\u003e\r\n\t\t\t\t\u003c/td\u003e\r\n\t\t\t\t\u003ctd style\u003d\"width:24.2pt;border-top:none;border-left:none;\r\n border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;padding:0in 5.4pt 0in 5.4pt\" valign\u003d\"top\" width\u003d\"32\"\u003e\r\n\t\t\t\t\t\u003cp align\u003d\"center\" class\u003d\"MsoNormal\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\r\n text-align:center\"\u003e\r\n\t\t\t\t\t\t0\u003c/p\u003e\r\n\t\t\t\t\u003c/td\u003e\r\n\t\t\t\u003c/tr\u003e\r\n\t\t\t\u003ctr\u003e\r\n\t\t\t\t\u003ctd style\u003d\"width:56.8pt;border:solid black 1.0pt;\r\n border-top:none;padding:0in 5.4pt 0in 5.4pt\" valign\u003d\"top\" width\u003d\"76\"\u003e\r\n\t\t\t\t\t\u003cp align\u003d\"center\" class\u003d\"MsoNormal\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\r\n text-align:center\"\u003e\r\n\t\t\t\t\t\tACCT\u003c/p\u003e\r\n\t\t\t\t\u003c/td\u003e\r\n\t\t\t\t\u003ctd style\u003d\"width:24.2pt;border-top:none;border-left:none;\r\n border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;padding:0in 5.4pt 0in 5.4pt\" valign\u003d\"top\" width\u003d\"32\"\u003e\r\n\t\t\t\t\t\u003cp align\u003d\"center\" class\u003d\"MsoNormal\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\r\n text-align:center\"\u003e\r\n\t\t\t\t\t\t1\u003c/p\u003e\r\n\t\t\t\t\u003c/td\u003e\r\n\t\t\t\u003c/tr\u003e\r\n\t\t\t\u003ctr\u003e\r\n\t\t\t\t\u003ctd style\u003d\"width:56.8pt;border:solid black 1.0pt;\r\n border-top:none;padding:0in 5.4pt 0in 5.4pt\" valign\u003d\"top\" width\u003d\"76\"\u003e\r\n\t\t\t\t\t\u003cp align\u003d\"center\" class\u003d\"MsoNormal\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\r\n text-align:center\"\u003e\r\n\t\t\t\t\t\t\u003cspan data-scayt_word\u003d\"ACCCT\" data-scaytid\u003d\"8\"\u003eACCCT\u003c/span\u003e\u003c/p\u003e\r\n\t\t\t\t\u003c/td\u003e\r\n\t\t\t\t\u003ctd style\u003d\"width:24.2pt;border-top:none;border-left:none;\r\n border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;padding:0in 5.4pt 0in 5.4pt\" valign\u003d\"top\" width\u003d\"32\"\u003e\r\n\t\t\t\t\t\u003cp align\u003d\"center\" class\u003d\"MsoNormal\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\r\n text-align:center\"\u003e\r\n\t\t\t\t\t\t0\u003c/p\u003e\r\n\t\t\t\t\u003c/td\u003e\r\n\t\t\t\u003c/tr\u003e\r\n\t\t\t\u003ctr\u003e\r\n\t\t\t\t\u003ctd style\u003d\"width:56.8pt;border:solid black 1.0pt;\r\n border-top:none;padding:0in 5.4pt 0in 5.4pt\" valign\u003d\"top\" width\u003d\"76\"\u003e\r\n\t\t\t\t\t\u003cp align\u003d\"center\" class\u003d\"MsoNormal\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\r\n text-align:center\"\u003e\r\n\t\t\t\t\t\t\u003cspan data-scayt_word\u003d\"ACCCCT\" data-scaytid\u003d\"9\"\u003eACCCCT\u003c/span\u003e\u003c/p\u003e\r\n\t\t\t\t\u003c/td\u003e\r\n\t\t\t\t\u003ctd style\u003d\"width:24.2pt;border-top:none;border-left:none;\r\n border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;padding:0in 5.4pt 0in 5.4pt\" valign\u003d\"top\" width\u003d\"32\"\u003e\r\n\t\t\t\t\t\u003cp align\u003d\"center\" class\u003d\"MsoNormal\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\r\n text-align:center\"\u003e\r\n\t\t\t\t\t\t1\u003c/p\u003e\r\n\t\t\t\t\u003c/td\u003e\r\n\t\t\t\u003c/tr\u003e\r\n\t\t\t\u003ctr\u003e\r\n\t\t\t\t\u003ctd style\u003d\"width:56.8pt;border:solid black 1.0pt;\r\n border-top:none;padding:0in 5.4pt 0in 5.4pt\" valign\u003d\"top\" width\u003d\"76\"\u003e\r\n\t\t\t\t\t\u003cp align\u003d\"center\" class\u003d\"MsoNormal\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\r\n text-align:center\"\u003e\r\n\t\t\t\t\t\t\u003cb\u003eTotal\u003c/b\u003e\u003c/p\u003e\r\n\t\t\t\t\u003c/td\u003e\r\n\t\t\t\t\u003ctd style\u003d\"width:24.2pt;border-top:none;border-left:none;\r\n border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;padding:0in 5.4pt 0in 5.4pt\" valign\u003d\"top\" width\u003d\"32\"\u003e\r\n\t\t\t\t\t\u003cp align\u003d\"center\" class\u003d\"MsoNormal\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\r\n text-align:center\"\u003e\r\n\t\t\t\t\t\t\u003cb\u003e6\u003c/b\u003e\u003c/p\u003e\r\n\t\t\t\t\u003c/td\u003e\r\n\t\t\t\u003c/tr\u003e\r\n\t\t\u003c/tbody\u003e\r\n\t\u003c/table\u003e\r\n\u003c/div\u003e\r\n\u003cp class\u003d\"MsoNormal\" style\u003d\"margin-top:10.0pt\"\u003e\r\n\tAs 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.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp class\u003d\"MsoNormal\"\u003e\r\n\tInput starts with an integer \u003cb\u003eT (\u003c/b\u003e\u003cb\u003e\u0026le; 20)\u003c/b\u003e, denoting the number of test cases.\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNormal\"\u003e\r\n\tEach 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 \u003cb\u003e50000\u003c/b\u003e and consists of only \u003cb\u003eA, C, T\u003c/b\u003e and \u003cb\u003eG\u003c/b\u003e.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp class\u003d\"MsoNormal\"\u003e\r\n\tFor each case, print the case number and the contribution, as described above.\u003c/p\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cp\u003e\r\n\t\u0026nbsp;\u003c/p\u003e\r\n\u003cp\u003e\r\n\t3\u003c/p\u003e\r\n\u003cp\u003e\r\n\t\u003cspan data-scayt_word\u003d\"ACTACCTACCCCT\" data-scaytid\u003d\"17\"\u003eACTACCTACCCCT\u003c/span\u003e\u003c/p\u003e\r\n\u003cp\u003e\r\n\tACCT\u003c/p\u003e\r\n\u003cp\u003e\r\n\tAAA\u003c/p\u003e\r\n\u003cp\u003e\r\n\t\u003cspan data-scayt_word\u003d\"AAAA\" data-scaytid\u003d\"18\"\u003eAAAA\u003c/span\u003e\u003c/p\u003e\r\n\u003cp\u003e\r\n\t\u003cspan data-scayt_word\u003d\"AAAA\" data-scaytid\u003d\"19\"\u003eAAAA\u003c/span\u003e\u003c/p\u003e\r\n\u003cp\u003e\r\n\tAAA\u003c/p\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cp\u003e\r\n\t\u0026nbsp;\u003c/p\u003e\r\n\u003cp\u003e\r\n\tCase 1: 6\u003c/p\u003e\r\n\u003cp\u003e\r\n\tCase 2: 4\u003c/p\u003e\r\n\u003cp\u003e\r\n\tCase 3: 8\u003c/p\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cp class\u003d\"MsoListParagraphCxSpFirst\" style\u003d\"text-align:justify;text-indent:-.25in\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;line-height:115%;font-family:\u0026quot;Garamond\u0026quot;,\u0026quot;serif\u0026quot;\"\u003e1.\u003cspan style\u003d\"font:7.0pt \u0026quot;Times New Roman\u0026quot;\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; \u003c/span\u003e\u003c/span\u003e\u003cspan style\u003d\"font-size:12.0pt;line-height:115%;font-family:\u0026quot;Garamond\u0026quot;,\u0026quot;serif\u0026quot;\"\u003eProper prefix (suffix) of a string \u003cb\u003eS\u003c/b\u003e is a prefix (suffix) of length smaller than \u003cb\u003e|S|\u003c/b\u003e. Here \u003cb\u003e|S|\u003c/b\u003e denotes length of \u003cb\u003eS\u003c/b\u003e.\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoListParagraphCxSpLast\" style\u003d\"text-align:justify;text-indent:-.25in\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;line-height:115%;font-family:\u0026quot;Garamond\u0026quot;,\u0026quot;serif\u0026quot;\"\u003e2.\u003cspan style\u003d\"font:7.0pt \u0026quot;Times New Roman\u0026quot;\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; \u003c/span\u003e\u003c/span\u003e\u003cspan style\u003d\"font-size:12.0pt;line-height:115%;font-family:\u0026quot;Garamond\u0026quot;,\u0026quot;serif\u0026quot;\"\u003eDataset is huge, use faster I/O methods.\u003c/span\u003e\u003c/p\u003e"}}]}