import java.util.*;

public class Solution {

	static final long MOD = 1000000007;

	public static long modInverse(long a) {
		long m = MOD;
		long y = 0, x = 1;
		while (a > 1) {
			long quotient = a / m;
			long remainder = a % m;

			a = m;
			m = remainder;

			long temp = y;
			y = x - quotient * y;
			x = temp;
		}

		return (x + MOD) % MOD;
	}

	public static int evaluatePostfix(String[] exp) {
		Stack<Long> stack = new Stack<>();

		for (String str : exp) {
			switch (str) {
				case "+":
					stack.push((stack.pop() + stack.pop()) % MOD);
					break;
				case "-":
					long subtractor = stack.pop();
					long difference = (stack.pop() - subtractor + MOD) % MOD;
					stack.push(difference);
					break;
				case "*":
					stack.push((stack.pop() * stack.pop()) % MOD);
					break;
				case "/":
					long inverse = modInverse(stack.pop());
					stack.push((stack.pop() * inverse) % MOD);
					break;
				default:
					stack.push(Long.parseLong(str));
					break;
			}
		}

		return stack.peek().intValue();
	}
}

import java.util.*;
import java.io.*;

public class Solution {
    public static Boolean isReflectionEqual(String s) {
        String str = "AHIMOTUVWXY";
        for (char ch : s.toCharArray()) {
            if (str.indexOf(ch) == -1)
                return false;
        }
        return new StringBuilder(s).reverse().toString().equals(s);
    }
}

import java.util.*;
import java.io.*;

public class Solution {

    private static String count(String ans) {
        StringBuilder temp = new StringBuilder();
        int count = 1;
        for (int i = 1; i < ans.length(); i++) {
            if (ans.charAt(i) == ans.charAt(i - 1))
                count++;
            else {
                temp.append(count).append(ans.charAt(i - 1));
                count = 1;
            }
        }
        temp.append(count).append(ans.charAt(ans.length() - 1));
        return temp.toString();
    }

    public static String writeAsYouSpeak(int n) {
        
        String ans = "1";
        for (int i = 2; i <= n; i++) {
            ans = count(ans);
        }
        return ans;
    }
}

import java.util.*;
import java.io.*;

public class Solution {
    static int[] detectOdd(int n, int nums[]) {
        
        int xor = 0;
        for (int i : nums) {
            xor ^= i;
        }

        int x = 0, y = 0;
        int setBit = xor & -xor;

        for (int i : nums) {
            if ((i & setBit) == 0) {
                x ^= i;
            } else {
                y ^= i;
            }
        }
        if(x < y)
            return new int[]{x,y};
        return new int[]{y,x};
    }
}

import java.util.*;
import java.io.*;


public class Solution {
    public static int countColumns(String[] strings) {
        int count = 0;
        for (int i = 0; i < strings[0].length(); i++) {
            boolean ans = false; // initialized to false


            for (int j = 0; j < strings.length - 1; j++) {
                if (strings[j].charAt(i) > strings[j + 1].charAt(i)) {
                    ans = true; // mark as unsorted column
                    break;
                }
            }
            count += ans ? 1 : 0;
        }
        return count;
    }
}