"QAQ" is a word to denote an expression of crying. Imagine "Q" as eyes with tears and "A" as a mouth.

Now Diamond has given Bort a string consisting of only uppercase English letters of length n. There is a great number of "QAQ" in the string (Diamond is so cute!).

<image> illustration by 猫屋 https://twitter.com/nekoyaliu

Bort wants to know how many subsequences "QAQ" are in the string Diamond has given. Note that the letters "QAQ" don't have to be consecutive, but the order of letters should be exact.

Input

The only line contains a string of length n (1 ≤ n ≤ 100). It's guaranteed that the string only contains uppercase English letters.

Output

Print a single integer — the number of subsequences "QAQ" in the string.

Examples

Input

QAQAQYSYIOIWIN


Output

4


Input

QAQQQZZYNOIWIN


Output

3

Note

In the first example there are 4 subsequences "QAQ": "QAQAQYSYIOIWIN", "QAQAQYSYIOIWIN", "QAQAQYSYIOIWIN", "QAQAQYSYIOIWIN".
import java.util.*;
import java.io.*;
 
public class Main {
	static InputReader scn = new InputReader(System.in);
	static OutputWriter out = new OutputWriter(System.out);
	public static void main(String[] args) {
		// Running Number Of TestCases (t)
		int t = 1;
		while(t-- > 0)
			solve();
		out.close();
	}
 

	public static void dummy(){
		// Dummy Code for Rough
		int a = BaseChange(22, 4);
		out.println(a);
	}

	static int[] dp;
	public static void solve() {
		// Main Solution (AC)
		String s = scn.next();
		int ans = 0;
		int n = s.length();
		int[][] dp = new int[n][2];
		int j = n - 1, sumS = 0, sumE = 0;
		for(int i = 0; i < n; i++){
			char chS = s.charAt(i);
			char chE = s.charAt(j);
			if(chS == 'Q'){
				sumS++;
			}
			if(chE == 'Q'){
				sumE++;
			}
			dp[i][0] = sumS;
			dp[j][1] = sumE;
			j--;
		}
		for(int i = 1; i + 1 < n; i++){
			char ch = s.charAt(i);
			if(ch == 'A'){
				int left = dp[i-1][0];
				int right = dp[i+1][0];
				int min = dp[i-1][0] * dp[i+1][1];
				ans += min;
			}
		}
		out.println(ans);
	}


	public static HashMap<Integer, Integer> sortByValue(HashMap<Integer, Integer> hm) {
        List<Map.Entry<Integer, Integer> > list = new LinkedList<Map.Entry<Integer, Integer> >(hm.entrySet());
        Collections.sort(list, new Comparator<Map.Entry<Integer, Integer> >() { 
            public int compare(Map.Entry<Integer, Integer> o1,  
                               Map.Entry<Integer, Integer> o2){ 
                return (o1.getValue()).compareTo(o2.getValue()); 
            } 
        });
        HashMap<Integer, Integer> temp = new LinkedHashMap<Integer, Integer>(); 
        for (Map.Entry<Integer, Integer> aa : list) { 
            temp.put(aa.getKey(), aa.getValue()); 
        } 
        return temp; 
    } 

	public static void sortbyColumn(int[][] arr, int col) {
		Arrays.sort(arr, new Comparator<int[]>() {
			public int compare(final int[] entry1, final int[] entry2) {
				if (entry1[col] > entry2[col])
					return 1;
				else
					return -1;
			}
		});
	}

	public static int BaseChange(int n, int r){
    	int i = 0;
    	int ans = 0;
    	while(n != 0){
    		int a = n % 10;
    		n /= 10;
    		ans += a * (Math.pow(r, i));
    		i++;
    	}
    	return ans;
    }
 
	public static HashSet<Long> primeFactors(long n, HashSet<Long> list, int d) {
		list.add(1L);
		list.add(n);
		for (long i = 2; i <= Math.sqrt(n); i += 1) {
			long a = i;
			if (n % a == 0) {
				list.add(a);
				if (n % (n / a) == 0)
					list.add(n / a);
			}
		}
		return list;
	}
 
	public static HashMap<Integer, Integer> CountFrequencies(int[] arr) {
		HashMap<Integer, Integer> map = new HashMap<>();
		for (int i : arr) {
			if (map.containsKey(i))
				map.put(i, map.get(i) + 1);
			else
				map.put(i, 1);
		}
		return map;
	}
 
	public static void ArraySort2D(int[][] arr, int xy) {
		// xy == 0, for sorting wrt X-Axis
		// xy == 1, for sorting wrt Y-Axis
		Arrays.sort(arr, Comparator.comparingDouble(o -> o[xy]));
	}
 
	public static long gcd(long a, long b) {
		if (a == 0)
			return b;
		return gcd(b % a, a);
	}
 
	public static long lcm(long a, long b) {
		return (a * b) / gcd(a, b);
	}
 
	public static boolean isPrime(long n) {
		if (n < 2)
			return false;
		if (n == 2 || n == 3)
			return true;
		if (n % 2 == 0 || n % 3 == 0)
			return false;
		long sqrtN = (long) Math.sqrt(n) + 1;
		for (long i = 6L; i <= sqrtN; i += 6) {
			if (n % (i - 1) == 0 || n % (i + 1) == 0)
				return false;
		}
		return true;
	}
 
	public static int firstOccurence(int array1[], int low, int high, int x, int n) {
		if (low <= high) {
			int mid = low + (high - low) / 2;
			if ((mid == 0 || x > array1[mid - 1]) && array1[mid] == x)
				return mid;
			else if (x > array1[mid])
				return firstOccurence(array1, (mid + 1), high, x, n);
			else
				return firstOccurence(array1, low, (mid - 1), x, n);
		}
		return -1;
	}
 
	public static int lastOccurence(int array2[], int low, int high, int x, int n) {
		if (low <= high) {
			int mid = low + (high - low) / 2;
			if ((mid == n - 1 || x < array2[mid + 1]) && array2[mid] == x)
				return mid;
			else if (x < array2[mid])
				return lastOccurence(array2, low, (mid - 1), x, n);
			else
				return lastOccurence(array2, (mid + 1), high, x, n);
		}
		return -1;
	}
 
	public static void quickSort(int[] arr, int lo, int hi) {
		if (lo >= hi) {
			return;
		}
		int mid = (lo + hi) / 2;
		int pivot = arr[mid];
		int left = lo;
		int right = hi;
		while (left <= right) {
			while (arr[left] < pivot) {
				left++;
			}
			while (arr[right] > pivot) {
				right--;
			}
			if (left <= right) {
				int temp = arr[left];
				arr[left] = arr[right];
				arr[right] = temp;
				left++;
				right--;
			}
		}
		quickSort(arr, lo, right);
		quickSort(arr, left, hi);
	}
 
	static class InputReader {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;
		private SpaceCharFilter filter;
 
		public InputReader(InputStream stream) {
			this.stream = stream;
		}
 
		public int[] readArrays(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++) {
				a[i] = scn.nextInt();
			}
			return a;
		}
 
		public int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}
 
		public int nextInt() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
 
		public long nextLong() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
 
		public String nextLine() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}
 
		public boolean isSpaceChar(int c) {
			if (filter != null)
				return filter.isSpaceChar(c);
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
 
		public String next() {
			return nextLine();
		}
 
		public interface SpaceCharFilter {
			public boolean isSpaceChar(int ch);
		}
	}
 
	static class OutputWriter {
		private final PrintWriter writer;
 
		public OutputWriter(OutputStream outputStream) {
			writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
		}
 
		public OutputWriter(Writer writer) {
			this.writer = new PrintWriter(writer);
		}
 
		public void print(Object... objects) {
			for (int i = 0; i < objects.length; i++) {
				if (i != 0) {
					writer.print(' ');
//                    writer.print(1);
				}
				writer.print(objects[i]);
			}
		}
 
		public void println(Object... objects) {
			print(objects);
			writer.println();
		}
 
		public void close() {
			writer.close();
		}
	}
 
}