"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.*;


public class Project1{
  static void solutionP2(){}
   static void selectionsort(int[] a){
        int t,ind;
        for (int i = 0; i < a.length; i++) {
            ind=i;
            for (int j = i+1; j < a.length; j++) {
            if(a[j]<a[i]){ind=j;}    
            }
            t=a[ind];a[ind]=a[i];a[i]=t;
        }
        for (int i : a) {
            System.out.print(i+" ");
        }
    }
  static void solutionP1(){solutionP2();}
   static void bubblesort(int [] a){
       int t,flag;
       for (int i = 1; i < a.length; i++) {
           flag=0;
           for (int j =0; j <a.length-i; j++) {
               if(a[j]>a[j+1]){t=a[j+1];a[j+1]=a[j];a[j]=t;flag=1;}
           }
          if(flag==0)break;
       }
       for (int i :a) {
           System.out.print(i+" ");
       }
   }
   static void fun(){
       solutionP1();
   }
   static void insertionsort(int[]a){
       List<Integer>list=new ArrayList();
       list.add(0,a[0]);
       int ind=0;
       for (int i = 1; i < a.length; i++) {
         ind=0;
       
           while(a[i]>list.get(ind)&&ind<list.size()){ind++;}
           list.add(ind,a[i]);
         
       }
       System.out.println(list);
   }
 //merge sort
   
   // Merges two subarrays of arr[]. 
    // First subarray is arr[l..m] L(index) to m
    // Second subarray is arr[m+1..r] m+one to r
   static void merge(int arr[], int l, int m, int r) 
    { 
        // Find sizes of two subarrays to be merged 
        int n1 = m - l + 1; 
        int n2 = r - m; 
  
        /* Create temp arrays */
        int L[] = new int [n1]; 
        int R[] = new int [n2]; 
  
        /*Copy data to temp arrays*/
        for (int i=0; i<n1; ++i) 
            L[i] = arr[l + i]; 
        for (int j=0; j<n2; ++j) 
            R[j] = arr[m + 1+ j]; 
  
  
        /* Merge the temp arrays */
  
        // Initial indexes of first and second subarrays 
        int i = 0, j = 0; 
  
        // Initial index of merged subarry array 
        int k = l; 
        while (i < n1 && j < n2) 
        { 
            if (L[i] <= R[j]) 
            { 
                arr[k] = L[i]; 
                i++; 
            } 
            else
            { 
                arr[k] = R[j]; 
                j++; 
            } 
            k++; 
        } 
  
        /* Copy remaining elements of L[] if any */
        while (i < n1) 
        { 
            arr[k] = L[i]; 
            i++; 
            k++; 
        } 
  
        /* Copy remaining elements of R[] if any */
        while (j < n2) 
        { 
            arr[k] = R[j]; 
            j++; 
            k++; 
        } 
    } 
  
    // Main function that sorts arr[l..r] using 
    // merge() 
   static void sort(int arr[], int l, int r) 
    { 
        if (l < r) 
        { 
            // Find the middle point 
            int m = (l+r)/2; 
  
            // Sort first and second halves 
            sort(arr, l, m); 
            sort(arr , m+1, r); 
  
            // Merge the sorted halves 
            merge(arr, l, m, r); 
        } 
    } 
  
    /* A utility function to print array of size n */
    static void printArray(int arr[]) 
    { 
        int n = arr.length; 
        for (int i=0; i<n; ++i) 
            System.out.print(arr[i] + " "); 
        System.out.println(); 
    } 
  
    // Driver method 
    static int fac(int a,int b){
        int min=Math.min(a, b),min2=min-1;
        while(min2>0){min*=min2--;}
        return min;
    }
    
    public static void main(String[] args) {
         Scanner sc=new Scanner(System.in);
         String s=sc.nextLine();int sm=0;
         if(s.contains("Q")&&s.contains("A")){
         s=s.substring(s.indexOf("Q"),s.lastIndexOf("Q")+1);
         String s2=s;
         while(s.contains("Q")){
         while(s.contains("A")){
             for (int i = s.indexOf("A"); i < s.length(); i++) {
                 sm+=s.charAt(i)=='Q'?1:0;
             }s=s.replaceFirst("A","a");
         }s2=s2.replaceFirst("Q","q");s=s2;if(s.contains("Q")){s=s.substring(s.indexOf("Q"));}
         }}
         System.out.println(sm);
 sc.close();}   
}