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

public class E24 {
    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        OutputWriter out = new OutputWriter(System.out);
        int n = in.nextInt();
        int k = in.nextInt();
        ArrayList<Integer> primes = new ArrayList<>();
        ArrayList<Integer> needed = new ArrayList<>();
        factorize(k, primes, needed);
        int primesSize = primes.size();
//        System.out.println("primes " + primes);
//        System.out.println("needed " + needed);
        
        ArrayList<ArrayList<Integer>> card = new ArrayList<>(n + 1);
        card.add(new ArrayList<>(Collections.nCopies(primesSize, 0)));
        for(int i = 0; i < n; ++i) {
            int value = in.nextInt();
            card.add(new ArrayList<>(primesSize));
            for(int prime: primes) {
                int cnt = 0;
                while(value % prime == 0) {
                    cnt++;
                    value /= prime;
                }
                card.get(i + 1).add(cnt);
            }
        }
//        for(int i = 0; i <= n; ++i) {
//            System.out.println("card " + i + ":" + card.get(i));
//        }
        
        int[] curState = new int[primesSize];
        boolean isFine = true;
        int ptr1 = 1;
        int ptr2 = 0;
        long ans = 0;
        for(; ptr1 <= n; ++ptr1) {
            //1. subtract previous cards factors
            for(int i = 0; i < primesSize; ++i) {
                curState[i] -= card.get(ptr1 - 1).get(i);
                if(curState[i] < needed.get(i)) {
                    isFine = false;
                }
            }
            //2. move ptr2 until all factors are satisfied
            while(ptr2 < n && !isFine) {
                ptr2++;
                isFine = true;
                for(int i = 0; i < primesSize; ++i) {
                    curState[i] += card.get(ptr2).get(i);
                    if(curState[i] < needed.get(i)) {
                        isFine = false;
                    }
                }
            }
            //3. calculate number of different combinations
            if(!isFine) {
                break;
            } else {
                ptr2 = Integer.max(ptr1, ptr2);
                ans += n - ptr2 + 1;
            }
        }
        System.out.println(ans);
        return;
    }
    
    static void factorize(int n, ArrayList<Integer> primes, ArrayList<Integer> needed) {
        int cnt;
        if(n % 2 == 0) {
            primes.add(2);
            cnt = 0;
            while(n % 2 == 0) {
                cnt++;
                n /= 2;
            }
            needed.add(cnt);
        }
        for(int i = 3; i * i <= n; i += 2) {
            if(n % i == 0) {
                primes.add(i);
                cnt = 0;
                while(n % i == 0) {
                    cnt++;
                    n /= i;
                }
                needed.add(cnt);
            }
        }
        if(n != 1) {
            primes.add(n);
            needed.add(1);
        }
    }

    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(objects[i]);
            }
        }

        public void println(Object... objects) {
            print(objects);
            writer.println();
        }

        public void printf(String format, Object... objects) {
            writer.printf(format, objects);
        }

        public void close() {
            writer.close();
        }

        public void flush() {
            writer.flush();
        }

    }
    
    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (this.numChars == -1) {
                throw new InputMismatchException();
            } else {
                if (this.curChar >= this.numChars) {
                    this.curChar = 0;

                    try {
                        this.numChars = this.stream.read(this.buf);
                    } catch (IOException var2) {
                        throw new InputMismatchException();
                    }

                    if (this.numChars <= 0) {
                        return -1;
                    }
                }

                return this.buf[this.curChar++];
            }
        }

        public int nextInt() {
            int c;
            for (c = this.read(); isSpaceChar(c); c = this.read()) {
                ;
            }

            byte sgn = 1;
            if (c == 45) {
                sgn = -1;
                c = this.read();
            }

            int res = 0;

            while (c >= 48 && c <= 57) {
                res *= 10;
                res += c - 48;
                c = this.read();
                if (isSpaceChar(c)) {
                    return res * sgn;
                }
            }

            throw new InputMismatchException();
        }

        public static boolean isSpaceChar(int c) {
            return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
        }

    }
}
