A string is k palindrome if it can be transformed into a palindrome on removing at most k characters from it. Your task is to complete the function is_k_palin which takes two arguments a string str and a number N . Your function should return true if the string is k palindrome else it should return false.
Input:
The first line of input is an integer T denoting the number of test cases . Then T test cases follow . Each test case  contains a string str and an integer N separated by space.  
Output:
The output will be 1 if the string is  k palindrome else 0 .
Constraints:
1<=T<=100
1<=length of str<=100
1<=N<=20
Example:
Input
2
abcdecba 1
acdcb  1
Output
1
0

Difficulty: EASY
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:
#You are required to complete this function
#your function should return an integer
def is_k_palin(string, n):
    #Code here

Solutions:
def is_k_palin(string, n):
	k = n
	n = len(string)
	dp = [[-1 for j in range(n)] for i in range(n)]
	for i in range(n - 1, -1, -1):
		for j in range(n):
			if i >= j:
				dp[i][j] = 0
			elif string[i] == string[j]:
				dp[i][j] = dp[i + 1][j - 1]
			else:
				dp[i][j] = 1 + min(dp[i + 1][j], dp[i][j - 1])
	if dp[0][n - 1] <= k:
		return 1
	return 0


def is_k_palin(string, n1):
	n = len(string)
	str1 = string[::-1]
	dp = [[None for i in range(n + 1)] for j in range(n + 1)]
	for i in range(n + 1):
		for j in range(n + 1):
			if i == 0 or j == 0:
				dp[i][j] = 0
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			if string[i - 1] == str1[j - 1]:
				dp[i][j] = 1 + dp[i - 1][j - 1]
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
	if n - dp[n][n] <= n1:
		return 1
	else:
		return 0


def is_k_palin(string, n):
	l = len(string)
	p = LPS(string, l)
	if l - p <= n:
		return 1
	return 0

def LPS(s, n):
	dp = [[0 for i in range(n)] for j in range(n)]
	for i in range(n):
		dp[i][i] = 1
	for l in range(2, n + 1):
		for i in range(n - l + 1):
			j = i + l - 1
			if s[i] == s[j]:
				dp[i][j] = 2 + dp[i + 1][j - 1]
			else:
				dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
	return dp[0][n - 1]


def is_k_palin(string, n):
	m = len(string)
	dp = [[0 for i in range(m + 1)] for j in range(m + 1)]
	r = string[::-1]
	for i in range(m - 1, -1, -1):
		for j in range(m - 1, -1, -1):
			if string[i] == r[j]:
				dp[i][j] = 1 + dp[i + 1][j + 1]
			else:
				dp[i][j] = max(dp[i][j + 1], dp[i + 1][j])
	x = m - dp[0][0]
	if x <= n:
		return 1
	return 0


def is_k_palin(string, n):
	return helper(string, n, {})

def helper(string, n, store):
	if len(string) < 2:
		return 1
	if string in store:
		return store[string]
	if n == 0:
		store[string] = int(string == string[::-1])
		return store[string]
	if string[0] == string[-1]:
		store[string] = helper(string[1:-1], n, store)
		return store[string]
	if helper(string[1:], n - 1, store):
		store[string] = 1
		return 1
	if helper(string[:-1], n - 1, store):
		store[string] = 1
		return 1
	store[string] = 0
	return 0


def lcs(s1, s2):
	n = len(s1)
	m = len(s2)
	dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			if s1[i - 1] == s2[j - 1]:
				dp[i][j] = 1 + dp[i - 1][j - 1]
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
	return dp[n][m]

def is_k_palin(string, n):
	s1 = string
	s2 = string[::-1]
	l = lcs(s1, s2)
	if len(s1) - l <= n:
		return 1
	else:
		return 0


def is_k_palin(string, k):
	n = len(string)
	prev = [0] * (n + 1)
	s = string
	t = string[::-1]
	for i in range(1, n + 1):
		curr = [0] * (n + 1)
		for j in range(1, n + 1):
			if s[i - 1] == t[j - 1]:
				curr[j] = prev[j - 1] + 1
			else:
				curr[j] = max(prev[j], curr[j - 1])
		prev = curr
	res = prev[n]
	return 1 if n - res <= k else 0


def is_k_palin(string, k):
	n = len(string)
	dp = [[0] * (n + 1) for _ in range(n + 1)]
	s = string
	t = string[::-1]
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			if s[i - 1] == t[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + 1
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
	res = dp[n][n]
	return 1 if n - res <= k else 0


def is_k_palin(string, k):
	rev_s = string[::-1]
	n = len(string)
	tab = []
	for i in range(n + 1):
		ls = [-1] * (n + 1)
		tab.append(ls)
	for i in range(n + 1):
		tab[i][0] = 0
		tab[0][i] = 0
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			if string[i - 1] == rev_s[j - 1]:
				tab[i][j] = 1 + tab[i - 1][j - 1]
			else:
				tab[i][j] = max(tab[i - 1][j], tab[i][j - 1])
	if n - tab[n][n] <= k:
		return 1
	else:
		return 0


def is_k_palin(s, m):
	r = list(s)
	r.reverse()
	n = len(s)
	dp = [[0] * (n + 1) for i in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			nottake = max(dp[i - 1][j], dp[i][j - 1])
			take = 0
			if s[i - 1] == r[j - 1]:
				take = 1 + dp[i - 1][j - 1]
			dp[i][j] = max(take, nottake)
	num = n - dp[n][n]
	if num <= m:
		return 1
	return 0


def is_k_palin(string, n):
	rs = ''.join(reversed(string))
	return edit_dst(string, rs, n)

def edit_dst(a, b, k):
	n = len(b)
	dp = [[0] * (n + 1) for _ in range(n + 1)]
	for i in range(n + 1):
		for j in range(n + 1):
			if i == 0:
				dp[i][j] = j
			elif j == 0:
				dp[i][j] = i
			elif a[i - 1] == b[j - 1]:
				dp[i][j] = dp[i - 1][j - 1]
			else:
				dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1])
	if dp[n][n] <= 2 * k:
		return 1
	else:
		return 0


def is_k_palin(string, k):
	StringRev = string[::-1]
	n = len(string)
	dp = [[0] * (n + 1) for _ in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			if StringRev[i - 1] == string[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + 1
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
	temp = n - dp[n][n]
	return 1 if temp <= k else 0


def is_k_palin(s, n):
	memo = {}

	def solve(i, j, k):
		if k < 0:
			return 0
		if i >= j:
			return 1
		if (i, j, k) in memo:
			return memo[i, j, k]
		memo[i, j, k] = s[i] == s[j] and solve(i + 1, j - 1, k)
		memo[i, j, k] = memo[i, j, k] or solve(i + 1, j, k - 1)
		memo[i, j, k] = memo[i, j, k] or solve(i, j - 1, k - 1)
		return memo[i, j, k]
	return solve(0, len(s) - 1, n)


def is_k_palin(S, n):

	def solve(S, i, j, n, dp):
		if i > j:
			return True
		if n < 0:
			return False
		if (i, j, n) in dp:
			return dp[i, j, n]
		if S[i] == S[j]:
			dp[i, j, n] = solve(S, i + 1, j - 1, n, dp)
			return dp[i, j, n]
		else:
			dp[i, j, n] = solve(S, i + 1, j, n - 1, dp) or solve(S, i, j - 1, n - 1, dp)
			return dp[i, j, n]
	dp = {}
	ans = solve(S, 0, len(S) - 1, n, dp)
	if ans:
		return 1
	return 0


def is_k_palin(string, k):
	n = len(string)
	str1 = string[::-1]
	l = [[0 for i in range(n + 1)] for j in range(n + 1)]
	for i in range(n + 1):
		for j in range(n + 1):
			if i != 0 and j != 0:
				if string[i - 1] == str1[j - 1]:
					l[i][j] = l[i - 1][j - 1] + 1
				else:
					l[i][j] = max(l[i - 1][j], l[i][j - 1])
	if n - l[n][n] <= k:
		return 1
	return 0


def solve(string, n, solutions={}):
	if n < 0:
		return False
	elif string in solutions:
		return solutions[string]
	elif len(string) <= 1:
		solutions[string] = True
		return solutions[string]
	elif string[0] == string[-1]:
		solutions[string] = solve(string[1:-1], n)
		return solutions[string]
	else:
		solutions[string] = solve(string[1:], n - 1) or solve(string[:-1], n - 1)
		return solutions[string]

def is_k_palin(string, n):
	sol = {}
	return int(solve(string, n, {}))


def is_k_palin(x, k):
	y = x[::-1]
	m = len(x)
	n = m
	dp = [[0 for i in range(n + 1)] for j in range(m + 1)]
	for i in range(m + 1):
		for j in range(n + 1):
			if not i:
				dp[i][j] = j
			elif not j:
				dp[i][j] = i
			elif x[i - 1] == y[j - 1]:
				dp[i][j] = dp[i - 1][j - 1]
			else:
				dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j])
	return 1 if dp[m][n] <= k * 2 else 0


def is_k_palin(str1, k):
	str2 = str1[::-1]
	m = len(str1)
	n = m
	dp = [[0] * (n + 1) for _ in range(m + 1)]
	for i in range(m + 1):
		for j in range(n + 1):
			if not i:
				dp[i][j] = j
			elif not j:
				dp[i][j] = i
			elif str1[i - 1] == str2[j - 1]:
				dp[i][j] = dp[i - 1][j - 1]
			else:
				dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1])
	return 1 if dp[m][n] <= k * 2 else 0


def is_k_palin(string, n):
	ls = len(string)
	dp = [[0] * ls for _ in range(ls)]
	for l in range(2, ls + 1):
		for i in range(ls - l + 1):
			if string[i] == string[l + i - 1]:
				dp[i][l + i - 1] = dp[i + 1][l + i - 2]
			else:
				dp[i][l + i - 1] = 1 + min(dp[i + 1][l + i - 1], dp[i][l + i - 2])
	if dp[0][-1] <= n:
		return 1
	return 0


def solve(s, rev, n):
	dp = [[0] * (n + 1) for _ in range(n + 1)]
	for i in range(0, n + 1):
		for j in range(0, n + 1):
			if not i or not j:
				dp[i][j] = 0
			elif s[i - 1] == rev[j - 1]:
				dp[i][j] = 1 + dp[i - 1][j - 1]
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
	return dp[n][n]

def is_k_palin(s, k):
	n = len(s)
	lcs = solve(s, s[::-1], n)
	return 1 if n - lcs <= k else 0


def is_k_palin(s, k):
	n = len(s)
	dp = [[0 for i in range(n)] for j in range(n)]
	m = 0
	for g in range(n):
		i = 0
		j = i + g
		while j < n:
			if g == 0:
				dp[i][j] = 1
			elif g == 1:
				if s[i] == s[j]:
					dp[i][j] = 2
				else:
					dp[i][j] = 1
			elif s[i] == s[j]:
				dp[i][j] = 2 + dp[i + 1][j - 1]
			else:
				dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
			m = max(m, dp[i][j])
			i += 1
			j += 1
	return int(n - m <= k)
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		arr = input().strip().split()
		string = arr[0]
		n = int(arr[1])
		print(is_k_palin(string, n))


def is_k_palin(string, n):

	def LCS(X, Y, m, n, t):
		if m == 0 or n == 0:
			return 0
		if t[m][n] != -1:
			return t[m][n]
		if X[m - 1] == Y[n - 1]:
			t[m][n] = 1 + LCS(X, Y, m - 1, n - 1, t)
			return t[m][n]
		else:
			t[m][n] = max(LCS(X, Y, m, n - 1, t), LCS(X, Y, m - 1, n, t))
			return t[m][n]
	a = string
	b = a[::-1]
	m = len(a)
	s = len(b)
	t = [[-1 for j in range(s + 1)] for i in range(m + 1)]
	e = LCS(a, b, m, s, t)
	j = m - e
	if j <= n:
		return 1
	elif j > n:
		return 0
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		arr = input().strip().split()
		string = arr[0]
		n = int(arr[1])
		print(is_k_palin(string, n))


def is_k_palin(string, n):
	s = string
	dp = [[0 for i in range(len(s))] for i in range(len(s))]
	for gap in range(len(s)):
		for i in range(len(s)):
			j = i + gap
			if j > len(s) - 1:
				break
			if gap == 0:
				dp[i][j] = 1
			elif gap == 1:
				if s[i] == s[j]:
					dp[i][j] = 2
				else:
					dp[i][j] = 1
			elif s[i] == s[j]:
				dp[i][j] = dp[i + 1][j - 1] + 2
			else:
				dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
	if len(s) - dp[0][-1] <= n:
		return 1
	else:
		return 0


def is_k_palin(string, n):
	length = len(string)
	dp = [[0] * (length + 1) for i in range(length + 1)]
	string1 = string[::-1]
	for i in range(1, length + 1):
		for j in range(1, length + 1):
			if string[i - 1] == string1[j - 1]:
				dp[i][j] = 1 + dp[i - 1][j - 1]
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
	diff = length - dp[length][length]
	if diff <= n:
		return 1
	return 0


def is_k_palin(string, n):
	k = 0
	l = len(string)
	i = 0
	j = l - 1
	if l < n:
		return 1
	while i < j and k <= n + 1:
		if string[i] == string[j]:
			i += 1
			j -= 1
		else:
			if j - i < n - k:
				return 1
			distance = 1
			search = 0
			while search < n - k + 1:
				if string[i + distance] == string[j - search]:
					i += distance + 1
					j -= search + 1
					k += distance + search
					search = 0
					break
				elif string[j - distance] == string[i + search]:
					j -= distance + 1
					i += search + 1
					k += distance + search
					search = 0
					break
				elif distance == n - k:
					distance = search + 1
					search += 1
				else:
					distance += 1
			if search > n - k:
				return 0
		if k > n:
			return 0
	return 1


def is_k_palin(string, n):

	def lcs(s1, s2, n):
		dp = [[0 for i in range(n + 1)] for j in range(n + 1)]
		for i in range(n + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
				elif s1[i - 1] == s2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[n][n]
	ans = lcs(string, string[::-1], len(string))
	if len(string) - ans <= n:
		return 1
	else:
		return 0


def is_k_palin(s, k):
	s2 = s[::-1]
	n = len(s)
	dp = [[0 for i in range(n + 1)] for i in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			if s[i - 1] == s2[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + 1
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
	if n - dp[n][n] <= k:
		return 1
	else:
		return 0


def is_k_palin(string, n):
	data = [[-1 for i in range(len(string) + 2)] for i in range(len(string) + 2)]

	def kappa(string, n, data):
		l = len(string)
		if l < 2:
			return 1
		for i in range(int(l / 2)):
			if string[i] != string[l - i - 1]:
				if n > 0:
					if data[i][i + 1] == -1:
						data[i][i + 1] = kappa(string[:i] + string[i + 1:], n - 1, data)
					if data[l - 1 - i][l - i] == -1:
						data[l - 1 - i][l - i] = kappa(string[:l - 1 - i] + string[l - i:], n - 1, data)
					return max(data[i][i + 1], data[l - 1 - i][l - i])
				else:
					return 0
		return 1
	return kappa(string, n, data)


def check_k_pali(s, k, memo):
	if len(s) == 1 or k >= len(s):
		return True
	elif s + str(k) in memo.keys():
		return memo[s + str(k)]
	elif s[0] != s[-1] and k <= 0:
		return False
	elif s[0] == s[-1]:
		return check_k_pali(s[1:-1], k, memo)
	else:
		memo[s + str(k)] = check_k_pali(s[0:-1], k - 1, memo) or check_k_pali(s[1:], k - 1, memo)
		return memo[s + str(k)]

def is_k_palin(string, n):
	memo = {}
	ans = 0
	if check_k_pali(string, n, memo):
		ans = 1
	return ans


def is_k_palin(string, n):
	X = string
	Y = string[::-1]
	ans = lcs(X, Y)
	if len(X) - ans <= n:
		return 1
	return 0

def lcs(X, Y):
	dp = []
	d = []
	for i in range(len(Y) + 1):
		d.append(0)
	for i in range(len(X) + 1):
		dp.append(d)
	for i in range(len(X) + 1):
		for j in range(len(X) + 1):
			if i == 0 or j == 0:
				dp[i][j] = 0
			elif X[i - 1] == Y[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + 1
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
	return dp[len(X)][len(Y)]


def lcs(x, y, m, n):
	L = [[0] * (n + 1) for _ in range(m + 1)]
	for i in range(n + 1):
		for j in range(n + 1):
			if not i or not j:
				L[i][j] = 0
			elif x[i - 1] == y[j - 1]:
				L[i][j] = L[i - 1][j - 1] + 1
			else:
				L[i][j] = max(L[i - 1][j], L[i][j - 1])
	return L

def is_k_palin(string, n):
	rev = string[::-1]
	full = len(string)
	dp = lcs(string, rev, full, full)
	if full - dp[full][full] <= n:
		return 1
	return 0


def is_k_palin(string, n):
	str1 = string[::-1]
	length = len(str1)
	t = [[0 for x in range(length + 1)] for y in range(length + 1)]
	for i in range(1, length + 1):
		for j in range(1, length + 1):
			if string[i - 1] == str1[j - 1]:
				t[i][j] = t[i - 1][j - 1] + 1
			else:
				t[i][j] = max(t[i - 1][j], t[i][j - 1])
	if length - t[length][length] <= n:
		return 1
	return 0


def lcs(string, revStr, m, n):
	dp = [[0] * (n + 1) for i in range(m + 1)]
	for i in range(m + 1):
		for j in range(n + 1):
			if not i or not j:
				dp[i][j] = 0
			elif string[i - 1] == revStr[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + 1
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
	return dp[m][n]

def is_k_palin(string, n):
	N = len(string)
	revStr = string[::-1]
	longest = lcs(string, revStr, N, N)
	if N - longest <= n:
		return 1
	return 0


def is_k_palin(str, k):
	if len(str) == 1:
		return 0
	start = 0
	end = len(str) - 1
	while start <= end:
		if str[start] != str[end]:
			if k > 0:
				k -= 1
				if str[start] == str[end - 1]:
					start -= 1
				else:
					end += 1
			else:
				return 0
		start += 1
		end -= 1
	return 1


def is_k_palin(string, n):
	N = len(string)
	revString = string[::-1]
	dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
	for i in range(1, N + 1):
		for j in range(1, N + 1):
			if string[i - 1] == revString[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + 1
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
	palindrome = N - dp[N][N]
	if palindrome <= n:
		return 1
	else:
		return 0


def is_k_palin(s1, k):
	s2 = s1[::-1]
	n1 = len(s1)
	n2 = len(s2)
	dp = [[0 for i in range(n2 + 1)] for j in range(n1 + 1)]
	for i in range(n1 + 1):
		for j in range(n2 + 1):
			if i == 0 or j == 0:
				dp[i][j] = 0
			elif s1[i - 1] == s2[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + 1
			else:
				dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
	return 1 if n1 - dp[n1][n2] <= k else 0


def is_k_palin(s, k):
	n = len(s)
	if k >= n:
		return 1
	s1 = s[::-1]
	t = [[0] * (n + 1) for i in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			if s[i - 1] == s1[j - 1]:
				t[i][j] = 1 + t[i - 1][j - 1]
			else:
				t[i][j] = max(t[i - 1][j], t[i][j - 1])
	r = n - t[n][n]
	if r <= k:
		return 1
	else:
		return 0


def is_k_palin(string, n):

	def lcs(s1, s2, x):
		dp = [[0 for i in range(x + 1)] for j in range(x + 1)]
		for i in range(1, x + 1):
			for j in range(1, x + 1):
				if s1[i - 1] == s2[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[x][x]
	s1 = string
	s2 = string[::-1]
	x = len(s1)
	if x - lcs(s1, s2, x) > n:
		return 0
	return 1


def longestCommonSubseq(str1, str2):
	n1 = len(str1)
	n2 = len(str2)
	dp = [[0 for _ in range(n2 + 1)] for _ in range(n1 + 1)]
	for i in range(1, n1 + 1):
		for j in range(1, n2 + 1):
			if str1[i - 1] == str2[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + 1
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
	return dp[-1][-1]

def is_k_palin(string, k):
	n = len(string)
	lcs = longestCommonSubseq(string, string[::-1])
	return int(n - lcs <= k)


def makeSameWord(str1, str2):
	n1 = len(str1)
	n2 = len(str2)
	dp = [[0 for _ in range(n2 + 1)] for _ in range(n1 + 1)]
	for i in range(n1 + 1):
		for j in range(n2 + 1):
			if i == 0:
				dp[i][j] = j
			elif j == 0:
				dp[i][j] = i
			elif str1[i - 1] == str2[j - 1]:
				dp[i][j] = dp[i - 1][j - 1]
			else:
				dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1
	return dp[n1][n2]

def is_k_palin(string, n):
	m = makeSameWord(string, string[::-1])
	return 1 if m <= n * 2 else 0


def isKPalDP(str1, str2, m, n):
	dp = [[0] * (n + 1) for _ in range(m + 1)]
	for i in range(m + 1):
		for j in range(n + 1):
			if not i:
				dp[i][j] = j
			elif not j:
				dp[i][j] = i
			elif str1[i - 1] == str2[j - 1]:
				dp[i][j] = dp[i - 1][j - 1]
			else:
				dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1])
	return dp[m][n]

def is_k_palin(string, k):
	revStr = string[::-1]
	l = len(string)
	res = isKPalDP(string, revStr, l, l) <= k * 2
	return 1 if res else 0


def is_k_palin(s, k):
	reverse = s[::-1]
	n = len(s)
	dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
	for i in range(n + 1):
		for j in range(n + 1):
			if i == 0:
				dp[i][j] = j
			elif j == 0:
				dp[i][j] = i
			elif s[i - 1] == reverse[j - 1]:
				dp[i][j] = dp[i - 1][j - 1]
			else:
				dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1])
	return 1 if dp[n][n] <= k * 2 else 0


def is_k_palin(s, n):
	revString = string[::-1]
	dp = [[0] * (len(string) + 1) for _ in range(len(string) + 1)]
	for i in range(len(string) + 1):
		for j in range(len(revString) + 1):
			if i == 0:
				dp[i][j] = j
			elif j == 0:
				dp[i][j] = i
			elif string[i - 1] == revString[j - 1]:
				dp[i][j] = dp[i - 1][j - 1]
			else:
				dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1])
	return 1 if dp[-1][-1] <= n * 2 else 0


def is_k_palin(string, n):
	length = len(string)
	s = ''.join(reversed(string))
	dp = [[0 for i in range(len(string) + 1)] for i in range(len(string) + 1)]
	for i in range(len(string) + 1):
		for j in range(len(string) + 1):
			if i == 0 or j == 0:
				dp[i][j] = 0
			elif string[i - 1] == s[j - 1]:
				dp[i][j] = 1 + dp[i - 1][j - 1]
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
	x = len(string) - dp[length][length]
	if x <= n:
		return 1
	else:
		return 0


def lcs(a, b):
	m = len(a)
	n = len(b)
	t = [[0 for i in range(m + 1)] for j in range(n + 1)]
	for i in range(1, m + 1):
		for j in range(1, n + 1):
			if a[i - 1] == b[j - 1]:
				t[i][j] = 1 + t[i - 1][j - 1]
			else:
				t[i][j] = max(t[i - 1][j], t[i][j - 1])
	return t[m][n]

def is_k_palin(s, n):
	lps = lcs(s, s[::-1])
	if len(s) - lps <= n:
		return 1
	return 0


def is_k_palin(s1, k):
	n = len(s1)
	s2 = s1[::-1]
	tab = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			if s1[i - 1] == s2[j - 1]:
				tab[i][j] = 1 + tab[i - 1][j - 1]
			else:
				tab[i][j] = max(tab[i - 1][j], tab[i][j - 1])
	if k >= n - tab[-1][-1]:
		return 1
	else:
		return 0


def is_k_palin(string, n):
	s = string
	r = s[::-1]
	s_l = len(s)
	r_l = len(r)
	dp = [[0] * (s_l + 1) for i in range(r_l + 1)]
	for i in range(1, r_l + 1):
		for j in range(1, s_l + 1):
			if s[j - 1] == r[i - 1]:
				dp[i][j] = 1 + dp[i - 1][j - 1]
			else:
				dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
	ans = s_l - dp[s_l][r_l]
	if ans <= n:
		return 1
	else:
		return 0


def is_k_palin(string, n):

	def solve(i, j, s, d):
		if i == j:
			return 1
		if i > j:
			return 0
		if (i, j) in d:
			return d[i, j]
		if s[i] == s[j]:
			temp = 2 + solve(i + 1, j - 1, s, d)
		else:
			temp = max(solve(i + 1, j, s, d), solve(i, j - 1, s, d))
		d[i, j] = temp
		return temp
	r = solve(0, len(string) - 1, string, {})
	rest = len(string) - r
	if rest <= n:
		return 1
	return 0


def is_k_palin(s1, n):
	s2 = s1[::-1]
	dp = []
	for i in range(len(s1) + 1):
		l = []
		for j in range(len(s1) + 1):
			l.append(0)
		dp.append(l)
	for i in range(1, len(s1) + 1):
		for j in range(1, len(s2) + 1):
			if s1[i - 1] == s2[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + 1
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
	x = dp[-1][-1]
	if len(s1) - x > n:
		return 0
	return 1


def is_k_palin(string, n):
	rev_string = string[::-1]
	l = len(string)
	table = [[None] * (l + 1) for i in range(l + 1)]
	for i in range(l + 1):
		for j in range(l + 1):
			if i == 0 or j == 0:
				table[i][j] = 0
			elif string[i - 1] == rev_string[j - 1]:
				table[i][j] = 1 + table[i - 1][j - 1]
			else:
				table[i][j] = max(table[i - 1][j], table[i][j - 1])
	lcs = table[l][l]
	if l - lcs <= n:
		return 1
	else:
		return 0


def is_k_palin(string, n):
	rev_string = string[::-1]
	a = b = len(string)
	table_matrix = [[None] * (b + 1) for i in range(a + 1)]
	for i in range(a + 1):
		for j in range(b + 1):
			if i == 0 or j == 0:
				table_matrix[i][j] = 0
			elif string[i - 1] == rev_string[j - 1]:
				table_matrix[i][j] = table_matrix[i - 1][j - 1] + 1
			else:
				table_matrix[i][j] = max(table_matrix[i - 1][j], table_matrix[i][j - 1])
	if a - table_matrix[a][b] <= n:
		return 1
	else:
		return 0


def is_k_palin(string, n):
	l = len(string)
	if n >= l:
		return 1
	rev = string[::-1]
	dp = [[0 for _i in range(l + 1)] for _ in range(l + 1)]
	for i in range(1, l + 1):
		for j in range(1, l + 1):
			if string[i - 1] == rev[j - 1]:
				dp[i][j] = 1 + dp[i - 1][j - 1]
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
	seq = ''
	i = j = l
	while i > 0 and j > 0:
		if dp[i - 1][j] == dp[i][j - 1]:
			i -= 1
			j -= 1
			if string[i] == rev[j]:
				seq += string[i]
		elif dp[i - 1][j] > dp[i][j - 1]:
			i -= 1
		else:
			j -= 1
	dela = l - dp[l][l]
	if n >= dela:
		return 1
	else:
		return 0


import functools

def is_k_palin(string, n):

	@functools.lru_cache(len(string))
	def sol(s, dff):
		if not s or dff < 0:
			return 0
		if s == s[::-1]:
			return 1
		j = len(s) - 1
		i = 0
		while i <= j:
			if s[i] == s[j]:
				i += 1
				j -= 1
			else:
				return sol(s[:i] + s[i + 1:], dff - 1) + sol(s[:j] + s[j + 1:], dff - 1)
	return min(sol(string, n), 1)


def is_k_palin(x, k):
	n = len(x)
	y = x[::-1]
	t = [[0] * (n + 1) for _ in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			if x[i - 1] == y[j - 1]:
				t[i][j] = 1 + t[i - 1][j - 1]
			else:
				t[i][j] = max(t[i - 1][j], t[i][j - 1])
	return int(n - t[-1][-1] <= k)


def is_k_palin(s, k):
	n = len(s)
	rev = s[::-1]
	dp = [list(range(n + 1)), list(range(n + 1))]
	for i in range(1, n + 1):
		dp[1][0] = i
		for j in range(1, n + 1):
			if s[i - 1] == rev[j - 1]:
				dp[1][j] = dp[0][j - 1]
			else:
				dp[1][j] = 1 + min(dp[0][j], dp[1][j - 1])
		dp[0] = dp[1][:]
	if dp[1][-1] <= 2 * k:
		return 1
	return 0


def is_k_palin(s, k):
	n = len(s)

	def lcs(x, y, m, n):
		l = [[0] * (n + 1) for _ in range(m + 1)]
		for i in range(m + 1):
			for j in range(n + 1):
				if not i or not j:
					l[i][j] = 0
				elif x[i - 1] == y[j - 1]:
					l[i][j] = l[i - 1][j - 1] + 1
				else:
					l[i][j] = max(l[i - 1][j], l[i][j - 1])
		return l[m][n]
	lps = lcs(s, s[::-1], n, n)
	return 1 if n - lps <= k else 0


def is_k_palin(s, k):
	n = len(s)
	dp = [[0 for i in range(n)] for j in range(n)]
	for l in range(1, n):
		for i in range(n):
			end = i + l
			if end >= n:
				break
			if s[i] == s[end]:
				dp[i][end] = dp[i + 1][end - 1]
			else:
				dp[i][end] = min(dp[i + 1][end] + 1, dp[i][end - 1] + 1)
	least_k = dp[0][n - 1]
	return 1 if k >= least_k else 0


def is_k_palin(string, n):
	dp = []
	l = len(string)
	for i in range(l + 1):
		a = [0] * (l + 1)
		dp.append(a)
	r = string[-1::-1]
	for i in range(1, l + 1):
		for j in range(1, l + 1):
			if r[j - 1] == string[i - 1]:
				dp[i][j] = dp[i - 1][j - 1] + 1
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
	if l - dp[l][l] <= n:
		return 1
	return 0


from functools import lru_cache

def is_k_palin(string, n):

	@lru_cache(None)
	def solve(start, end, k):
		if k < 0:
			return False
		if start >= end:
			return k >= 0
		if string[start] == string[end]:
			if solve(start + 1, end - 1, k):
				return True
		elif solve(start + 1, end, k - 1) or solve(start, end - 1, k - 1) or solve(start + 1, end - 1, k - 2):
			return True
		return False
	if solve(0, len(string) - 1, n):
		return 1
	else:
		return 0


def is_k_palin(string, n):
	dp = []
	for i in range(len(string) + 1):
		temp = []
		for j in range(len(string) + 1):
			temp.append(0)
		dp.append(temp)
	string2 = string[::-1]
	for i in range(len(string) + 1):
		for j in range(len(string) + 1):
			if i == 0 or j == 0:
				dp[i][j] = 0
			elif string[i - 1] == string2[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + 1
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
	c = dp[len(string)][len(string)]
	if len(string) - c <= n:
		return 1
	else:
		return 0


def helper(string, l, h, memo):
	if memo[l][h] == -1:
		if l >= h:
			res = 0
		elif string[l] == string[h - 1]:
			res = helper(string, l + 1, h - 1, memo)
		else:
			res = 1 + min(helper(string, l + 1, h, memo), helper(string, l, h - 1, memo))
		memo[l][h] = res
	return memo[l][h]

def is_k_palin(string, n):
	if n >= len(string):
		return 1
	memo = [[-1 for i in range(len(string) + 1)] for j in range(len(string) + 1)]
	return int(n >= helper(string, 0, len(string), memo))


def pall(s, left, right, k, d):
	if left > right:
		return False
	if left == right:
		return True
	if (left, right) in d.keys():
		return d[left, right]
	if s[left] == s[right]:
		d[left, right] = pall(s, left + 1, right - 1, k, d)
	elif k > 0:
		d[left, right] = pall(s, left + 1, right, k - 1, d) or pall(s, left, right - 1, k - 1, d)
	else:
		d[left, right] = False
	return d[left, right]

def is_k_palin(string, n):
	d = {}
	if pall(string, 0, len(string) - 1, n, d):
		return 1
	else:
		return 0