Vova again tries to play some computer card game.

The rules of deck creation in this game are simple. Vova is given an existing deck of n cards and a magic number k. The order of the cards in the deck is fixed. Each card has a number written on it; number ai is written on the i-th card in the deck.

After receiving the deck and the magic number, Vova removes x (possibly x = 0) cards from the top of the deck, y (possibly y = 0) cards from the bottom of the deck, and the rest of the deck is his new deck (Vova has to leave at least one card in the deck after removing cards). So Vova's new deck actually contains cards x + 1, x + 2, ... n - y - 1, n - y from the original deck.

Vova's new deck is considered valid iff the product of all numbers written on the cards in his new deck is divisible by k. So Vova received a deck (possibly not a valid one) and a number k, and now he wonders, how many ways are there to choose x and y so the deck he will get after removing x cards from the top and y cards from the bottom is valid?

Input

The first line contains two integers n and k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ 109).

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the numbers written on the cards.

Output

Print the number of ways to choose x and y so the resulting deck is valid.

Examples

Input

3 4
6 2 8


Output

4


Input

3 6
9 1 14


Output

1

Note

In the first example the possible values of x and y are:

  1. x = 0, y = 0; 
  2. x = 1, y = 0; 
  3. x = 2, y = 0; 
  4. x = 0, y = 1. 
import java.io.*;
import java.util.Arrays;
import java.util.HashMap;

public class Main {
    static myScanner sc;
    static PrintWriter pw;

    public static void main(String[] args) throws IOException {
        //setInAndOutPutFromFile("ladder");
        setDefaultInAndOutPut();

        int numberOfTests = 1;
        for (int test = 1; test <= numberOfTests; test++) {
            solve();
            pw.flush();
        }

        pw.close();
    }

    static void setDefaultInAndOutPut() {
        sc = new myScanner(new BufferedReader(new InputStreamReader(System.in)));
        pw = new PrintWriter(System.out);
    }

    static void setInAndOutPutFromFile(String s) throws IOException {
        sc = new myScanner(new BufferedReader(new FileReader(new File(s + ".in"))));
        pw = new PrintWriter(new File(s + ".out"));
    }

    static void solve() {
        int n=sc.nextInt(),k=sc.nextInt();

        HashMap<Integer,Integer> simpleDiv = new HashMap<>();

        for (int i=2;i*i<=1000000000;i++){
            int put = 0;
            while (k%i==0){
                put++;
                k/=i;
            }
            if (put>0)simpleDiv.put(i,put);
        }
        if (k!=1)simpleDiv.put(k,simpleDiv.getOrDefault(k,0)+1);
        int[] arr = new int[n];
        for (int i=0;i<n;i++)arr[i]=sc.nextInt();
        int r = 0;
        long ans= 0;
        for (int l=0;l<n;l++){
            boolean yeah = false;
            if (r==l){
                delFactFromArr(simpleDiv,arr[r],false);
                r++;
            }
            while (!(yeah=checkArr(simpleDiv)) && r<n){
                delFactFromArr(simpleDiv,arr[r],false);
                r++;
            }
            if (yeah)ans+=n-r+1;
            delFactFromArr(simpleDiv,arr[l],true);
        }
        pw.print(ans);
    }

    private static boolean checkArr(HashMap<Integer,Integer> map){
        for (int div:map.values())if (div>0)return false;
        return true;
    }
    private static void delFactFromArr(HashMap<Integer,Integer> map, int number,boolean ret) {
        for (int div:map.keySet()){
            int count = 0;
            while (number>1 && number%div==0){
                number/=div;
                count++;
            }
            if (!ret)count=-count;
            map.put(div,map.get(div)+count);
        }
    }

}

class myScanner {
    private char[] buffer = new char[1 << 8];
    private int pos = 1;

    private BufferedReader reader;

    public myScanner(BufferedReader reader) {
        this.reader = reader;
    }

    public boolean hasNext() {
        return pos > 0;
    }

    private void loadBuffer() {
        pos = 0;
        try {
            for (int i; (i = reader.read()) != -1; ) {
                char c = (char) i;
                if (c != ' ' && c != '\n' && c != '\t' && c != '\r' && c != '\f') {
                    if (pos == buffer.length) buffer = Arrays.copyOf(buffer, 2 * pos);
                    buffer[pos++] = c;
                } else if (pos != 0) break;
            }
        } catch (IOException e) {
            throw new UncheckedIOException(e);
        }
    }

    public String current() {
        return String.copyValueOf(buffer, 0, pos);
    }


    public String next() {
        loadBuffer();
        return current();
    }


    public String nextLine() {
        try {
            return reader.readLine();
        } catch (IOException e) {
            throw new UncheckedIOException(e);
        }
    }


    public int nextInt() {
        return nextInt(10);
    }

    public long nextLong() {
        return nextLong(10);
    }

    public int nextInt(int radix) {
        loadBuffer();
        int result = 0;
        int i = buffer[0] == '-' || buffer[0] == '+' ? 1 : 0;
        for (checkValidNumber(pos > i); i < pos; i++) {
            int digit = buffer[i] - '0';
            checkValidNumber(0 <= digit && digit <= radix - 1);
            result = result * radix + digit;
        }
        return buffer[0] == '-' ? -result : result;
    }

    public long nextLong(int radix) {
        loadBuffer();
        long result = 0;
        int i = buffer[0] == '-' || buffer[0] == '+' ? 1 : 0;
        for (checkValidNumber(pos > i); i < pos; i++) {
            int digit = buffer[i] - '0';
            checkValidNumber(0 <= digit && digit <= radix - 1);
            result = result * radix + digit;
        }
        return buffer[0] == '-' ? -result : result;
    }

    public double nextDouble() {
        loadBuffer();
        long result = 0;
        int i = buffer[0] == '-' || buffer[0] == '+' ? 1 : 0;
        long round = 1;
        final int radix = 10;
        boolean hasPoint = false;
        for (checkValidNumber(pos > i); i < pos; i++) {
            int digit = buffer[i] - '0';
            checkValidNumber((0 <= digit && digit <= radix - 1) || (!hasPoint && digit == -2));
            if (digit == -2) hasPoint = true;
            else {
                if (hasPoint) round *= radix;
                result = result * radix + digit;
            }

        }
        return buffer[0] == '-' ? -result / (1.0 * round) : result / (1.0 * round);
    }

    private void checkValidNumber(boolean condition) {
        if (!condition) throw new NumberFormatException(current());
    }
}