Arya has a string, s, of uppercase English letters. She writes down the string s on a paper k times. She wants to calculate the occurence of a specific letter  in the first n characters of the final string.
Example
Input : 
s = "ABA"
k = 3
n = 7
c = 'B'
Output : 
2
Explaination : 
Final string - ABAABAABA
Example 
Input : 
s = "MMM"
k = 2
n = 4
c = 'M'
Output :
4
Explaination : 
Final string - MMMMMM
Ã¢â¬â¹Your Task:
You don't need to read input or print anything. Your task is to complete the function fun() which takes the string s , integer k ,integer n and the character c as input parameter and returns the occurence of the character c  in the first n characters of the final string.
Expected Time Complexity : O(|s|)
Expected Auxiliary Space : O(1)
Constraints:
1 <= |s| <= 10^{5}
1 <= k <= 10^{5}
1 <= n <= |s|*k

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3

class Solution:

    def fun(self, s,k,n,c):
        # code here

Solutions:
class Solution:

	def fun(self, s, k, n, c):
		st = ''
		while k and n >= 0:
			st += s
			k -= 1
			n -= len(s)
		return st[:n].count(c)


class Solution:

	def fun(self, s, k, n, c):
		freq = 0
		for i in s:
			if i == c:
				freq += 1
		freq *= n // len(s)
		n = n % len(s)
		for i in range(n):
			if s[i] == c:
				freq += 1
		return freq


class Solution:

	def fun(self, s, k, n, c):
		if len(s) > n:
			return s[:n].count(c)
		ans = s.count(c)
		res = ans
		for i in range(k):
			n = n - len(s)
			if n < len(s):
				break
			else:
				res += ans
		for i in range(n):
			if s[i] == c:
				res += 1
		return res


class Solution:

	def fun(self, s, k, n, c):
		count = s.count(c)
		count = count * (n // len(s))
		rem = s[:n % len(s)]
		count += rem.count(c)
		return count


class Solution:

	def fun(self, s, k, n, c):
		if c not in set(s):
			return 0
		i = n % len(s)
		p = s.count(c)
		t = n // len(s) * p
		for j in range(i):
			if s[j] == c:
				t += 1
		return t


from collections import Counter

class Solution:

	def fun(self, s, k, n, c):
		lenght = len(s)
		count = 0
		count += Counter(s)[c] * (n // lenght)
		count += Counter(s[:n % lenght])[c]
		return count


class Solution:

	def fun(self, s, k, n, c):
		x = ''
		while len(x) <= n:
			x += s
		res = x[:n]
		res1 = res.count(c)
		return res1


class Solution:

	def fun(self, s, k, n, c):
		count = 0
		for i in s:
			if i == c:
				count += 1
		d = n // len(s)
		r = n % len(s)
		count = count * d
		for i in s[:r]:
			if i == c:
				count += 1
		return count


class Solution:

	def fun(self, s: str, k: int, n: int, c: str) -> int:
		count1 = 0
		for i in range(n % len(s)):
			if s[i] == c:
				count1 += 1
		count2 = 0
		for chr in s:
			if chr == c:
				count2 += 1
		return count1 + n // len(s) * count2


class Solution:

	def fun(self, s, k, n, c):
		l = []
		b = ''
		for i in range(k):
			if len(b) <= n:
				b += s
		return b[:n].count(c)


from math import ceil

class Solution:

	def fun(self, s, k, n, c):
		t = s * ceil(n / len(s))
		return t[:n].count(c)


class Solution:

	def fun(self, s, k, n, c):
		count = 0
		ch = 0
		for i in range(len(s)):
			if s[i] == c:
				ch += 1
		for i in range(int(n / len(s))):
			count += ch
		for i in range(n % len(s)):
			if s[i] == c:
				count += 1
		return count


import math

class Solution:

	def fun(self, s, k, n, c):
		l = len(s)
		res = 0
		for i in range(l):
			if s[i] == c:
				res += math.ceil((n - i) / l)
		return res


class Solution:

	def fun(self, s, k, n, c):
		c1 = s.count(c)
		r = n // len(s)
		re = n % len(s)
		ns = s[:re]
		nc = ns.count(c)
		res = c1 * r + nc
		return res


class Solution:

	def fun(self, s, k, n, c):
		count = 0
		size = len(s)
		read = int(n / size)
		left = int(n % size)
		for i in range(size):
			if s[i] == c:
				count = count + 1
		count = count * read
		for i in range(left):
			if s[i] == c:
				count = count + 1
		return int(count)


class Solution:

	def fun(self, s, k, n, c):
		m = ''
		for i in range(1, k + 1):
			m = m + s
			if len(m) > n:
				break
		m = m[:n]
		return m.count(c)


class Solution:

	def fun(self, s, k, n, c):
		sz = len(s)
		ans = 0
		for i in range(0, sz):
			if s[i] == c:
				ans += (n - i + sz - 1) // sz
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input()
		knc = input().split()
		k = int(knc[0])
		n = int(knc[1])
		c = knc[2]
		solObj = Solution()
		print(solObj.fun(s, k, n, c))


class Solution:

	def fun(self, s, k, n, c):
		z = n // len(s)
		y = n % len(s)
		ss = s.count(c) * z
		sss = s[:y].count(c)
		return ss + sss
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input()
		knc = input().split()
		k = int(knc[0])
		n = int(knc[1])
		c = knc[2]
		solObj = Solution()
		print(solObj.fun(s, k, n, c))


class Solution:

	def fun(self, s, k, n, c):
		read1 = n // len(s)
		left = n % len(s)
		count = 0
		for i in range(len(s)):
			if s[i] == c:
				count += 1
		count *= read1
		for i in range(left):
			if s[i] == c:
				count += 1
		return count


class Solution:

	def fun(self, s, k, n, c):
		k = n // len(s) + 1
		s = s * k
		return s.count(c, 0, n)


import math

class Solution:

	def fun(self, s, k, n, c):
		if n > len(s):
			l = s * math.ceil(n / len(s))
			m = l[:n].count(c)
		else:
			m = s[:n].count(c)
		return m


class Solution:

	def fun(self, s, k, n, c):
		ans = 0
		for i in s:
			if i == c:
				ans = ans + 1
		ans = ans * int(n / len(s))
		n = n - len(s) * int(n / len(s))
		s = s[0:n]
		for i in s:
			if i == c:
				ans = ans + 1
		return ans


class Solution:

	def fun(self, s, k, n, c):
		x = 0
		for i in s:
			if i == c:
				x += 1
		temp = 0
		if n % len(s) == 0:
			return x * (n // len(s))
		else:
			return x * (n // len(s)) + s[:n % len(s)].count(c)


class Solution:

	def fun(self, s, k, n, c):
		y = s.count(c)
		p = n // len(s)
		n = n % len(s)
		x = s[:n]
		t = x.count(c)
		return t + y * p


class Solution:

	def fun(self, s, k, n, c):
		count = 0
		occurence = s.count(c)
		perfect_hit = int(n / len(s))
		remaining = n % len(s)
		count = occurence * perfect_hit
		for x in s[:remaining]:
			if x == c:
				count += 1
		return count


class Solution:

	def fun(self, s, k, n, c):
		count = 0
		l = len(s)
		read = n // l
		left = n % l
		count = s.count(c)
		count = count * read
		count += s[:left].count(c)
		return count


from collections import Counter

class Solution:

	def fun(self, s, k, n, c):
		gg = Counter(s)
		ans = 0
		a = gg[c]
		l = len(s)
		k = n // l
		m = n % l
		ans += a * k
		for i in range(m):
			if s[i] == c:
				ans += 1
		return ans
		return ans


class Solution:

	def fun(self, s, k, n, c):
		count = s.count(c)
		x = n // len(s)
		count = count * x
		ranje = n % len(s)
		count += s[:ranje].count(c)
		return count


class Solution:

	def fun(self, s, k, n, c):
		s = s
		l = 0
		for i in range(0, len(s)):
			if s[i] == c:
				l += 1
		if n % len(s) == 0:
			return l * (n // len(s))
		else:
			x = l * (n // len(s))
			t = n % len(s)
			for i in range(0, t):
				if s[i] == c:
					x += 1
			return x


class Solution:

	def fun(self, s, k, n, c):
		occur = s.count(c)
		ot = n // len(s)
		remn = n % len(s)
		count = ot * occur
		for i in range(remn):
			if s[i] == c:
				count += 1
		return count


class Solution:

	def fun(self, s, k, n, c):
		l = len(s)
		a = list(s)
		counter = {}
		occ = 0
		for i in a:
			if i == c:
				occ += 1
		res = 0
		f = n // l
		r = n - l * f
		counter = 0
		for i in range(0, r):
			if a[i] == c:
				counter += 1
		res = counter + occ * f
		return res


class Solution:

	def fun(self, s, k, n, c):
		cnt = s.count(c)
		res = n // len(s) * cnt
		rem = n % len(s)
		for i in range(rem):
			if s[i] == c:
				res += 1
		return res


class Solution:

	def fun(self, s, k, n, c):
		count = 0
		l = len(s)
		le = n // l
		for i in range(l):
			if s[i] == c:
				count += 1
		count = count * le
		temp = n % l
		for j in range(temp):
			if s[j] == c:
				count += 1
		return count


class Solution:

	def fun(self, s, k, n, c):
		l = len(s)
		read = n // l
		left = n % l
		count1 = s.count(c) * read
		for i in range(left):
			if s[i] == c:
				count1 += 1
		return count1


class Solution:

	def fun(self, s, k, n, c):
		counter = 0
		x = len(s)
		if x > n:
			for i in range(n):
				if s[i] == c:
					counter += 1
			return counter
		for i in s:
			if i == c:
				counter += 1
		ans = counter * (n // x)
		if n % x != 0:
			for i in range(n % x):
				if s[i] == c:
					ans += 1
		return ans


class Solution:

	def fun(self, s, k, n, c):
		ks = s * (n // len(s)) + s[0:n % len(s)]
		h = ks.count(c)
		return h


class Solution:

	def fun(self, s, k, n, c):
		count = 0
		l = len(s)
		for i in s:
			if i == c:
				count += 1
		count *= n // l
		rem = n % l
		for i in range(rem):
			if c == s[i]:
				count += 1
		return count


class Solution:

	def fun(self, s, k, n, c):
		l = len(s)
		a = s.count(c)
		b = n // l
		d = n % l
		s = s[:d]
		e = s.count(c)
		return a * b + e


class Solution:

	def fun(self, s, k, n, c):
		l = len(s)
		st = s[:n % len(s)]
		ans = s.count(c)
		t = n // l
		ans *= t
		ans += st.count(c)
		return ans


class Solution:

	def fun(self, s, k, n, c):
		l = len(s)
		no_full = n // l
		no_part = n % l
		nf = 0
		np = 0
		for i in s:
			if i == c:
				nf += 1
		for i in s[:no_part]:
			if i == c:
				np += 1
		return no_full * nf + np


class Solution:

	def fun(self, s, k, n, c):
		a = 0
		sz = len(s)
		for i in range(0, sz):
			if s[i] == c:
				a += (n - i + sz - 1) / sz
				a = int(a)
		return a


class Solution:

	def fun(self, s, k, n, c):
		c1 = 0
		c2 = 0
		ln = len(s)
		for i in range(ln):
			if s[i] != c:
				continue
			if i < n % ln:
				c1 += 1
			c2 += 1
		return c1 + c2 * (n // ln)


class Solution:

	def fun(self, s, k, n, c):
		(count, cFull) = (0, 0)
		for char in s:
			if char == c:
				cFull += 1
		m = 0
		while len(s) * (m + 1) < n:
			m += 1
		for i in range(n - len(s) * m):
			if s[i] == c:
				count += 1
		return count + m * cFull


class Solution:

	def fun(self, s, k, n, c):
		kop = 0
		r = 0
		for j in range(len(s)):
			if s[j] == c:
				kop = kop + 1
		r = r + n // len(s) * kop
		n = n % len(s)
		for i in range(n):
			if s[i] == c:
				r = r + 1
		return r