def AdditivePersistence(num):
    count = 0
    while num >= 10:
        total = 0
        for digit in str(num):
            total += int(digit)
        num = total
        count += 1
    return count
    
def ArithGeo(arr):
    diff = arr[1] - arr[0]
    ratio = arr[1] / arr[0]
    
    is_arithmetic = True
    is_geometric = True
    
    for i in range(2, len(arr)):
        if arr[i] - arr[i-1] != diff:
            is_arithmetic = False
        if arr[i] / arr[i-1] != ratio:
            is_geometric = False
        
        # optimization: if both is_arithmetic and is_geometric are False, we can return -1
        if not is_arithmetic and not is_geometric:
            return -1
        
    if is_arithmetic:
        return "Arithmetic"
    elif is_geometric:
        return "Geometric"
    else:
        return -1
 
def ArrayMinJumps(arr):
  jumps = 0
  current_end = 0
  farthest = 0
  for i in range(len(arr)):
    if i + arr[i] >= len(arr) - 1:
      return jumps + 1
    farthest = max(farthest, i + arr[i])
    if i == current_end:
      current_end = farthest
      jumps += 1
    if current_end <= i:
      return -1

def ArrayRotation(arr):
  n = arr[0]
  rotated = arr[n:] + arr[:n]
  return "".join(str(x) for x in rotated)
  
def BracketCombinations(num):
    def generate_combinations(open_count, close_count):
        nonlocal count
        if open_count == num and close_count == num:
            count += 1
            return
        if open_count < num:
            generate_combinations(open_count+1, close_count)
        if close_count < open_count:
            generate_combinations(open_count, close_count+1)
        
    count = 0
    generate_combinations(0, 0)
    return count

def ChangingSequence(arr):
    direction = None

    for i in range(1, len(arr)):
        if direction is None:
            if arr[i] == arr[i-1]:
                continue
            elif arr[i] > arr[i-1]:
                direction = 'increasing'
            else:
                direction = 'decreasing'
        elif direction == 'increasing':
            if arr[i] <= arr[i-1]:
                return i - 1
        elif direction == 'decreasing':
            if arr[i] >= arr[i-1]:
                return i - 1
    
    return -1
    
def ClosestEnemy(arr):
    index_of_one = arr.index(1)
    min_dist = float('inf')
    for i in range(index_of_one, len(arr)):
        if arr[i] == 2:
            min_dist = min(min_dist, i - index_of_one)
            break
    for i in range(index_of_one, -1, -1):
        if arr[i] == 2:
            min_dist = min(min_dist, index_of_one - i)
            break
    return min_dist if min_dist != float('inf') else 0

import math

def CountingAnagrams(str):
    word_freq = {}

    words = str.split()

    for word in words:
        word = word.strip()
        sorted_word = ''.join(sorted(word))
        if sorted_word in word_freq:
            word_freq[sorted_word] += 1
        else:
            word_freq[sorted_word] = 1

    anagram_count = 0

    for freq in word_freq.values():
        if freq > 1 and freq != len(word_freq):
            anagram_count += math.comb(freq, 2)

    return anagram_count
    
def DistinctList(arr):
    distinct_numbers = set()
    duplicates = 0

    for num in arr:
        if num in distinct_numbers:
            duplicates += 1
        else:
            distinct_numbers.add(num)

    return duplicates

def ElementMerger(arr):
  new_arr = arr.copy()
  while len(new_arr) > 1:
    temp = []
    for i in range(1, len(new_arr)):
      diff = abs(new_arr[i] - new_arr[i-1])
      temp.append(diff)
    new_arr = temp.copy()
  return new_arr[0]

def EquivalentKeypresses(strArr):
    s1, s2 = strArr
    stack1, stack2 = [], []
    
    for ch in s1.split(','):
        if ch == '-B':
            if stack1:
                stack1.pop()
        else:
            stack1.append(ch)

    for ch in s2.split(','):
        if ch == '-B':
            if stack2:
                stack2.pop()
        else:
            stack2.append(ch)

    return stack1 == stack2
    
def FindIntersection(strArr):

  # code goes here
  l1 = set(map(int, strArr[0].split(",")))
  l2 = set(map(int, strArr[1].split(",")))

  intersection = l1.intersection(l2)

  if(len(intersection) == 0):
    return False
  else:
    sinter = sorted(intersection)
    return ",".join(map(str, sinter))
 
def GroupTotals(strArr):

  # code goes here
  total = {}

  for p in strArr:
    key, value = p.split(":")
    value = int (value)
    if key in total:
      total[key] += value
    else:
      total[key] = value

  result = []
  for key, value in total.items():
    if value != 0:
      result.append(f"{key}:{value}")

  return ",".join(sorted(result))
  
def HDistance(strArr):
  count = 0
  for i in range(len(strArr[0])):
    if strArr[0][i] != strArr[1][i]:
      count += 1
  return count
  
def HammingDistance(strArr):
    return sum(ch1 != ch2 for ch1, ch2 in zip(strArr[0], strArr[1]))
    
def HistogramArea(arr):
    stack = []
    max_area = 0
    for i, h in enumerate(arr):
        while stack and arr[stack[-1]] > h:
            height = arr[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            area = height * width
            max_area = max(max_area, area)
        stack.append(i)
    while stack:
        height = arr[stack.pop()]
        width = len(arr) if not stack else len(arr) - stack[-1] - 1
        area = height * width
        max_area = max(max_area, area)
    return max_area

def largest_four(arr):
    n = len(arr)
    if n <= 4:
        return sum(arr)
    arr.sort(reverse=True)
    return sum(arr[:4])
    
def longest_consecutive(arr):
    nums = set(arr)
    longest_sequence = 0
    for num in nums:
        if num-1 not in nums:
            current_sequence = 1
            while num+1 in nums:
                current_sequence += 1
                num += 1
            longest_sequence = max(longest_sequence, current_sequence)
    return longest_sequence

def LRUcache(strArr):
    cache = []
    for element in strArr:
        if element in cache:
            cache.remove(element)
        cache.insert(0, element)
        if len(cache) > 5:
            cache.pop()
    return '-'.join(cache)

def MaxSubarray(arr):
    max_so_far = float('-inf')
    max_ending_here = 0
    for i in range(len(arr)):
        max_ending_here += arr[i]
        if max_ending_here > max_so_far:
            max_so_far = max_ending_here
        if max_ending_here < 0:
            max_ending_here = 0
    return max_so_far
    
def NearestSmallerValues(arr):
    n = len(arr)
    result = []
    for i in range(n):
        j = i - 1
        while j >= 0:
            if arr[j] < arr[i]:
                result.append(str(arr[j]))
                break
            j -= 1
        if j < 0:
            result.append("-1")
    return " ".join(result)
    
def OffLineMinimum(strArr):
    result = []
    stack = []
    for char in strArr:
        if char.isdigit():
            stack.append(int(char))
        elif char == 'E':
            min_num = min(stack)
            result.append(str(min_num))
            stack.remove(min_num)
    return ",".join(result)
    
def OtherProducts(arr):
    result = []
    for i, num in enumerate(arr):
        product = 1
        for j, n in enumerate(arr):
            if i != j:
                product *= n
        result.append(str(product))
    return '-'.join(result)
    
def OverlappingRanges(arr):
    a, b, c, d, x = arr
    
    start = max(a, c)
    end = min(b, d)
    
    overlap_count = end - start + 1
    
    if overlap_count >= x:
        return "true"
    else:
        return "false"
        
def RectangleArea(strArr):
    # Step 1
    x1, y1 = map(int, strArr[0].strip('()').split())
    min_x = max_x = x1
    min_y = max_y = y1

    # Step 2
    for point in strArr[1:]:
        x, y = map(int, point.strip('()').split())
        if x < min_x:
            min_x = x
        elif x > max_x:
            max_x = x
        if y < min_y:
            min_y = y
        elif y > max_y:
            max_y = y

    # Step 3
    width = max_x - min_x
    # Step 4
    height = max_y - min_y
    # Step 5
    area = width * height
    # Step 6
    return area

def SecondGreatLow(arr):
    distinct_arr = list(set(arr))  # Remove duplicates
    sorted_arr = sorted(distinct_arr)  # Sort in ascending order

    if len(sorted_arr) == 2:
        return str(sorted_arr[1]) + " " + str(sorted_arr[0])
    else:
        return str(sorted_arr[1]) + " " + str(sorted_arr[-2])
        
def SumMultiplier(arr):
    total_sum = sum(arr)
    double_sum = total_sum * 2

    sorted_arr = sorted(arr, reverse=True)

    for i in range(len(sorted_arr) - 1):
        if sorted_arr[i] * sorted_arr[i+1] > double_sum:
            return "true"

    return "false"

def Superincreasing(arr):
    sum_so_far = 0

    for num in arr:
        if num <= sum_so_far:
            return "false"
        sum_so_far += num

    return "true"
    
def ThirdGreatest(strArr):
    sorted_arr = sorted(strArr, key=len, reverse=True)
    return sorted_arr[2]

def TreeConstructor(strArr):
    parent_children = {}
    for pair in strArr:
        i1, i2 = pair.strip('()').split(',')
        if i2 not in parent_children:
            parent_children[i2] = [i1]
        elif len(parent_children[i2]) == 2:
            return "false"
        else:
            parent_children[i2].append(i1)
    root_count = 0
    for parent in parent_children:
        if parent not in [child for children in parent_children.values() for child in children]:
            root_count += 1
    return "true" if root_count == 1 else "false"
    
def BinaryConverter(str):
    decimal = 0
    for ch in str:
        decimal = decimal * 2 + int(ch)
    return decimal

def Consecutive(arr):
    arr.sort()
    missing_count = 0
    for i in range(len(arr) - 1):
        missing_count += arr[i + 1] - arr[i] - 1
    return missing_count
    
import math

def FibonacciChecker(num):
    # check if num is a perfect square
    x = 5*num*num + 4
    y = 5*num*num - 4
    if int(math.sqrt(x))**2 == x or int(math.sqrt(y))**2 == y:
        return "yes"
    else:
        return "no"
        
def get_next_number(num):
    digit_squares = [int(digit) ** 2 for digit in str(num)]
    return sum(digit_squares)

def HappyNumbers(num):
    current_number = num
    visited = set()

    while current_number != 1 and current_number not in visited:
        visited.add(current_number)
        current_number = get_next_number(current_number)

    return current_number == 1
    
def MissingDigit(equation):
    num_list = equation.split()

    for i in range(len(num_list)):
        if 'x' in num_list[i]:
            for digit in range(10):
                num_list[i] = num_list[i].replace('x', str(digit))
                equation_str = ' '.join(num_list)
                if eval(equation_str):
                    return digit

    return None
def SimpleAdding(num):
    sum = 0
    for i in range(1, num+1):
        sum += i
    return sum

def SimpleEvens(num):
    num_str = str(num)
    for ch in num_str:
        if int(ch) % 2 != 0:
            return "false"
    return "true"

def ThreeFiveMultiples(num):
    # initialize sum to zero
    sum = 0
    # iterate over all numbers less than num
    for i in range(num):
        # if i is a multiple of 3 or 5, add it to the sum
        if i % 3 == 0 or i % 5 == 0:
            sum += i
    return sum
    
def ABCheck(str):
    str = str.lower()
    for i in range(len(str)):
        if str[i] == 'a' and i + 4 < len(str) and str[i+4] == 'b':
            return 'true'
    return 'false'

def AlphabetSearching(str):
    alphabet = set('abcdefghijklmnopqrstuvwxyz')
    for char in alphabet:
        if char not in str:
            return "false"
    return "true"
    
def AlphabetSoup(strParam):
  # Convert the input string to a list of characters
  chars = list(strParam)
  # Sort the list in alphabetical order
  chars.sort()
  # Join the characters back together into a string
  sorted_str = ''.join(chars)
  # Return the sorted string
  return sorted_str

def ASCIIConversion(strParam):
    result = ""
    for char in strParam:
        if char != " ":
            result += str(ord(char))
        else:
            result += " "
    return result
    
def BasicRomanNumerals(str):
    roman_to_decimal = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
    result = 0
    for i in range(len(str)):
        current_value = roman_to_decimal[str[i]]
        if i < len(str) - 1 and roman_to_decimal[str[i+1]] > current_value:
            result -= current_value
        else:
            result += current_value
    return result

def BinaryReversal(strParam):
    # Convert input string to integer
    num = int(strParam)
    # Convert integer to binary string
    binary_str = bin(num)
    # Remove '0b' prefix from binary string
    binary_str = binary_str[2:]
    # Calculate minimum number of bytes required to represent the binary string
    num_bytes = (len(binary_str) + 7) // 8
    # Pad binary string with leading zeros to make its length a multiple of 8
    binary_str = binary_str.zfill(num_bytes * 8)
    # Reverse binary string
    reversed_binary_str = binary_str[::-1]
    # Convert reversed binary string to decimal representation
    decimal_num = int(reversed_binary_str, 2)
    return str(decimal_num)

def DashInsert(Str):
    # convert str to a string
    Str = str(Str)
    # initialize an empty string for the result
    result = ""
    # iterate over the string, checking adjacent digits
    for i in range(len(Str)-1):
        # check if both digits are odd
        if int(Str[i]) % 2 == 1 and int(Str[i+1]) % 2 == 1:
            result += Str[i] + "-"
        else:
            result += Str[i]
    # add the last digit to the result
    result += Str[-1]
    return result
    
def DifferentCases(strparam):
    # convert str to lowercase
    strparam = strparam.lower()
    # split the string into words using delimiter punctuation characters
    words = re.split('[\W_]+', strparam)
    # capitalize the first letter of each word and concatenate the result
    return ''.join([word.capitalize() for word in words])

def DistinctCharacters(str):
    # create a set of the characters in the string
    chars = set(str)
    # check if the set has at least 10 elements
    if len(chars) >= 10:
        return "true"
    else:
        return "false"
        
def ExOh(str):
    count_x = 0
    count_o = 0
    for ch in str:
        if ch == 'x':
            count_x += 1
        elif ch == 'o':
            count_o += 1
    return count_x == count_o

def FirstReverse(strParam):
    result = ""
    for i in range(len(strParam) - 1, -1, -1):
        result += strParam[i]
    return result

def FizzBuzz(num):
    result = ""
    for i in range(1, num+1):
        if i % 3 == 0 and i % 5 == 0:
            result += "FizzBuzz "
        elif i % 3 == 0:
            result += "Fizz "
        elif i % 5 == 0:
            result += "Buzz "
        else:
            result += str(i) + " "
    return result.strip()
    
def FormattedNumber(strArr):
    # Get the input string from strArr
    input_string = strArr[0]
    
    # Remove all commas from the input string
    input_string = input_string.replace(",", "")
    
    # Split the input string into two parts by the decimal point
    parts = input_string.split(".")
    
    # Check that there are at most two parts, and that each part consists only of digits
    if len(parts) > 2 or not all(part.isdigit() for part in parts):
        return "false"
    
    # If there are two parts, check that the second part has no more than two digits
    if len(parts) == 2 and len(parts[1]) > 2:
        return "false"
    
    # Otherwise, the input is a properly formatted number
    return "true"

def FormattedDivision(num1, num2):
  result = num1 / num2
  formatted_result = '{:,.4f}'.format(result)
  return formatted_result
 
def LetterCapitalize(strParam):
    words = strParam.split()
    for i in range(len(words)):
        words[i] = words[i].capitalize()
    return " ".join(words)

def NumberEncoding(strparam):
    # Define a dictionary to map each letter to its corresponding position in the alphabet
    alphabet = {chr(i + ord('a')): str(i + 1) for i in range(26)}
    
    # Initialize an empty string to store the encoded message
    encoded = ""
    
    # Loop over each character in the input string
    for char in strparam:
        if char.isalpha():
            # If the character is a letter, add its corresponding number to the encoded string
            encoded += alphabet[char.lower()]
        else:
            # If the character is not a letter, add it to the encoded string as-is
            encoded += char
    
    return encoded

def OffBinary(strArr):
    # Convert the decimal number to binary and remove the "0b" prefix
    dec = int(strArr[0])
    bin_str = bin(dec)[2:]
    
    # Pad the binary string with leading zeros if necessary
    if len(bin_str) < len(strArr[1]):
        bin_str = "0"*(len(strArr[1])-len(bin_str)) + bin_str
    
    # Loop over the binary strings and count the number of different bits
    count = 0
    for i in range(len(bin_str)):
        if bin_str[i] != strArr[1][i]:
            count += 1
            
    return count
 
def OneDecremented(str):
    count = 0
    for i in range(1, len(str)):
        if int(str[i]) == int(str[i-1])-1:
            count += 1
    return count

def Palindrome(strParam):
    # Remove non-alphabetic characters and convert to lowercase
    strParam = "".join(ch.lower() for ch in strParam if ch.isalpha())

    # Reverse the string
    rev_str = strParam[::-1]

    # Compare original string with reversed string
    if strParam == rev_str:
        return "true"
    else:
        return "false"
        
def RunLength(strParam):
    if not strParam:
        return ""  # Return empty string if input is empty

    compressed_str = ""
    count = 1
    previous_char = strParam[0]

    for i in range(1, len(strParam)):
        current_char = strParam[i]

        if current_char == previous_char:
            count += 1
        else:
            compressed_str += str(count) + previous_char
            count = 1
            previous_char = current_char

    compressed_str += str(count) + previous_char
    return compressed_str
    
def SimplePassword(str):
    # Check if the string meets all the constraints
    if any(c.isupper() for c in str) and \
       any(c.isdigit() for c in str) and \
       any(c in "!@#$%^&*()-+?_=,<>/\|{}[]~" for c in str) and \
       "password" not in str.lower() and \
       7 < len(str) < 31:
           return "true"
    else:
        return "false"

def SimpleSymbols(strParam):
    strParam = strParam.lower()  # Convert the input string to lowercase for case-insensitive comparison

    for i in range(len(strParam)):
        if strParam[i].isalpha():
            if i == 0 or i == len(strParam) - 1:
                return "false"  # First or last character is a letter without surrounding symbols

            if strParam[i-1] != '+' or strParam[i+1] != '+':
                return "false"  # Letter without surrounding symbols

    return "true"  # All letters have correct surrounding symbols
    
def StarRating(str):
    rating = float(str)
    rounded_rating = round(rating * 2)
    full_stars = rounded_rating // 2
    empty_stars = 5 - full_stars
    has_half_star = rounded_rating % 2 != 0

    image_names = ["full"] * full_stars
    if has_half_star:
        image_names.append("half")
    image_names.extend(["empty"] * empty_stars)

    return " ".join(image_names)
    
def StringChanges(str):
    result = ""
    n = len(str)
    i = 0
    while i < n:
        if str[i] == "M":
            if i > 0:
                result += str[i-1] * 2
            i += 1
        elif str[i] == "N":
            i += 2
        else:
            result += str[i]
            i += 1
    return result

def StringScramble(string1, string2):
    array1 = list(string1)
    array2 = list(string2)

    i = 0
    while i < len(array1):
        j = 0
        while j < len(array2):
            if array1[i] == array2[j]:
                array1.pop(i)
                array2.pop(j)
                i -= 1
                break
            j += 1
        i += 1

    if len(array2) == 0:
        return True
    else:
        return False
        
def TimeConvert(num):
    hours = num // 60
    minutes = num % 60
    return str(hours) + ":" + str(minutes)
    
def CodelandUsernameValidation(str):
    if len(str) < 4 or len(str) > 25:
        return "false"
    if not str[0].isalpha():
        return "false"
    for c in str:
        if not (c.isalpha() or c.isdigit() or c == "_"):
            return "false"
    if str[-1] == "_":
        return "false"
    return "true"   

def VowelCount(str):
    vowels = "aeiouAEIOU" # Define the list of vowels
    count = 0 # Initialize count to 0

    # Iterate through each character in the input string
    for char in str:
        if char in vowels: # If the character is a vowel
            count += 1 # Increment count by 1

    return count # Return the total count of vowels in the string