"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.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.FilterInputStream;
import java.io.BufferedInputStream;
import java.util.LinkedList;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Jenish
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        ScanReader in = new ScanReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        QAQ solver = new QAQ();
        solver.solve(1, in, out);
        out.close();
    }

    static class QAQ {
        public void solve(int testNumber, ScanReader in, PrintWriter out) {


            String str = in.scanString();
            StringBuffer sb = new StringBuffer("");
            int n = str.length();
            for (int i = 0; i < n; i++) {
                if (str.charAt(i) == 'Q' || str.charAt(i) == 'A')
                    sb.append(str.charAt(i));
            }


            n = sb.length();

            LinkedList<Integer> ln[] = new LinkedList[n];
            for (int i = 0; i < n; i++) {
                ln[i] = new LinkedList<>();
            }
            int arr[] = new int[n];
            int q = 0;
            int a = 0;

            for (int i = n - 1; i >= 0; i--) {
                if (sb.charAt(i) == 'Q') {
                    arr[i] = a;
                    q++;
                } else {
                    arr[i] = q;
                    a++;
                }
            }


            for (int i = 0; i < n; i++) {
                if (sb.charAt(i) == 'Q')
                    for (int j = i + 1; j < n; j++) {
                        if (sb.charAt(j) == 'A')
                            ln[i].add(j);
                    }
            }


            int ans = 0;

            for (int i = 0; i < n; i++) {
                if (sb.charAt(i) == 'Q') {
                    for (int j = 0; j < ln[i].size(); j++) {
                        ans += arr[ln[i].get(j)];
                    }
                }
            }


            out.println(ans);

        }

    }

    static class ScanReader {
        private byte[] buf = new byte[4 * 1024];
        private int index;
        private BufferedInputStream in;
        private int total;

        public ScanReader(InputStream inputStream) {
            in = new BufferedInputStream(inputStream);
        }

        private int scan() {
            if (index >= total) {
                index = 0;
                try {
                    total = in.read(buf);
                } catch (Exception e) {
                    e.printStackTrace();
                    ;
                }
                if (total <= 0) return -1;
            }
            return buf[index++];
        }

        public String scanString() {
            int c = scan();
            while (isWhiteSpace(c)) c = scan();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = scan();
            } while (!isWhiteSpace(c));
            return res.toString();
        }

        private boolean isWhiteSpace(int n) {
            if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true;
            else return false;
        }

    }
}

