"Given an array of DISTINCT elements, rearrange the elements of an array in zig-zag fashion in O(n) time. The converted array should be in form a < b > c < d > e < f.

Example:

Input: arr[] = {4, 3, 7, 8, 6, 2, 1} Output: arr[] = {3, 7, 4, 8, 2, 6, 1}

Input: arr[] = {1, 4, 3, 2} Output: arr[] = {1, 4, 2, 3}"

Sneha is a student at Cummins College of engineering Pune. One day she has to distribute some chocolates to her friends. She is biased towards her friends and plans to give them more than the others. One of the professor hears of this and tells her to make sure everyone gets the same number. To make things difficult, she must equalize the number of chocolates in a series of operations. For each operation, she can give 1,2 or 5 pieces to all but not one friend. Everyone who gets a piece in a round receives the same number of pieces. Given a starting distribution, calculate the minimum number of operations needed so that every friend has the same number of pieces. Example: arr=[1,1,5] arr represents the starting numbers of pieces for each colleague. She can give 2 pieces to the first two and the distribution is then arr[3,3,5] . On the next round, she gives the same two 2 pieces each, and everyone has the same number arr[5,5,5]. Return the number of rounds, 2

Given a matrix of size n x m, where every row and column is sorted in increasing order, and a number x. Find whether element x is present in the matrix or not.

Example 1:

Input: n = 3, m = 3, x = 62 matrix[][] = {{ 3, 30, 38}, {36, 43, 60}, {40, 51, 69}} Output: 0

A recent survey suggested that almost everybody knows that a palindrome is a string which reads the same backwards as forwards. Recently, Blacky invented a brand-new concept: K-palindromes. A string is called a K-palindrome if it is possible to make it a usual palindrome by replacing at most K characters. For example, a string abb can be made a palindrome by replacing one character, the second b with an a. Please note, that according to the definition, a usual palindrome is a K-palindrome for any non-negative integer K.

Blacky was walking in a garden and came across a string S of N characters. Now, he wants to know the sum of the lengths of all substrings of S which are K-palindromes. Note that two substrings are considered to be different if they cover the different ranges of indices, even if they are equal as strings.

Input The first line of input contains an integer T denoting the number of test cases. Each of the next T lines contains a description of a separate test case.

The only line of the test case description contains two integers N and K followed by string S, all separated by single spaces. S consists of lowercase Latin characters only.

Output For each test case, output a single line containing one integer: the answer for the test case.

Constraints 1 ≤ T ≤ 5 1 ≤ N ≤ 105 0 ≤ K ≤ 5

Sample Input 1 2 7 0 abacaba 7 1 abacaba Sample Output 1 28 56

Explanation

Test case 1: There are: 7 0-palindromes with length 1 (just each character) 3 0-palindromes with length 3 (aba, aca, aba) 1 0-palindrome with length 5 (bacab) 1 0-palindrome with length 7 (abacaba) . The total length: 71 + 33 + 15 + 71 = 28

Test case 2: There are: 7 1-palindromes with length 1 (just each character) 6 1-palindromes with length 2 (each substring with length 2) 5 1-palindromes with length 3 (each substring with length 3) 3 1-palindromes with length 5 (abaca,bacab, acaba) 1 1-palindrome with length 7 (abacaba) . The total length: 71 + 62 + 53 + 53 + 7*1 = 56

Given a grid consisting of '0's(Water) and '1's(Land). Find the number of islands. Example 1:

Input: grid = {{0,1},{1,0},{1,1},{1,0}} Output: 1 Explanation: The grid is- 0 1 1 0 1 1 1 0 All lands are connected.

In a hospital, there's a waiting room with N chairs set in a single row. Chairs are consecutively numbered from 1 to N. The first chair is closest to the door.

For some reason people choose a chair that is:

1. as far from other people as possible
2. and as close to the door as possible All chairs must be occupied before the first person will be served. then Find the last patient's chair's number.

Input - N - integer greater than 2 - number of chairs. The output should be a positive integer too - the last patient's chair's number.

Example: Consider if N=10, the seating arrangement will be as following:

Chairs | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- Patients | 1 | 7 | 5 | 8 | 3 | 9 | 4 | 6 | 10 | 2

Thus, the last person's chair number is 9.

You are given an integer array nums.

You should move each element of nums into one of the two arrays A and B such that A and B are non-empty, and average(A) == average(B).

Return true if it is possible to achieve that and false otherwise.

Example 1: Input: nums = [1,2,3,4,5,6,7,8] Output: true Explanation: We can split the array into [1,4,5,8] and [2,3,6,7], and both of them have an average of 4.5.

An insect is crossing a road. The road is divided into some number of units, and at each unit, there may or may not exist a leaf. An insect can jump on a leaf, but it must not jump on road. Given a list of leaf's positions (in units) in sorted ascending order, determine if an insect can cross the road by landing on the last leaf. Initially, an insect is on the first leaf and assumes the first jump must be 1 unit.If insect's last jump was k units, its next jump must be either k - 1, k, or k + 1 units. An insect can only jump in the forward direction. eg: Input: leaves= [0,1,3,5,6,8,12,17] Output: true Explanation: An insect can jump to the last leaf by jumping 1 unit to the 2nd leaf, then 2 units to the 3rd leaf, then 2 units to the 4th leaf, then 3 units to the 6th leaf, 4 units to the 7th leaf, and 5 units to the 8th leaf. Input: leaves = [0,1,2,3,4,8,9,11] Output: false Explanation: There is no way to jump to the last leaf as the gap between the 5th and 6th leaf is too large.

Given an array arr[] of n integers. Check whether it contains a triplet that sums up to zero. example : Input: n = 5, arr[] = {0, -1, 2, -3, 1} Output: 1 Explanation: 0, -1 and 1 forms a triplet with sum equal to 0.

Given a string, find out the occurrence of each character in the string. For example, String = "apple", then in output it should print : a = 1, p = 2, l = 1 , e=1.

"Given an m x n matrix, return all elements of the matrix in spiral order and sorted order.

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [1,2,3,6,9,8,7,4,5] [1,2,3,4,5,6,7,8,9]"