Problem 1800: sugubatz

Cosmin was bored during the Romanian class when the teacher mentioned a mischievous character in the story "Povestea lui Harap-Alb." This reminded Cosmin of a tricky problem he couldn't solve. If you help him solve the problem, he will send you a mischievous elf with a violin and a bow. Thus, Cosmin will understand how to solve the problem, and you will enjoy harmonious music.

Task

You are given two numbers, $N$ and $X$ , followed by an array $A$ of $N$ non-zero natural numbers, indexed from $1$ to $N$ . A new array $B$ will be constructed, where each number $b_i$ ( $1 \leq i \leq N$ ) takes the largest value of the greatest common divisor that $a_i$ has with another number in the array $A$ . Determine the number of subarrays in array $B$ whose bitwise "OR" sum is greater than or equal to the number $X$ .

A subarray of array $B$ is a sequence of elements from different, consecutive positions.

The bitwise "OR" sum of a subarray $v_1, v_2, \dots, v_k$ is defined as $v_1 \vert v_2 \vert \dots \vert v_k$ , where $\vert$ signifies the bitwise "OR" operator.

Input data

The first line contains the natural numbers $N$ and $X$ , and the second line contains the $N$ natural numbers of the array $A$ . The numbers on the same line are separated by a space.

Output data

Print a single number representing the number of subarrays with the desired property.

Constraints and clarifications

$2 \leq N \leq 1 \ 000 \ 000$
$1 \leq X \leq 1 \ 000 \ 000$
$1 \leq a_i \leq 1 \ 000 \ 000$

#	Points	Constraints
1	22	$2 \leq N \leq 1 \ 000$
2	31	$2 \leq N \leq 100 \ 000$
3	47	No additional constraints

Note

Due to the very large input data, use the following instructions at the beginning of the main() function in your C++ program:

ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

Example

stdin

5 3
17 2 9 12 2

stdout

Explanation

After each number $b_i$ ( $1 \leq i \leq N$ ) takes the largest value of the greatest common divisor that $a_i$ has with another number in array $A$ , the array $B$ has values $1, 2, 3, 3, 2$ . In this new array, there are $12$ subarrays that have a bitwise "OR" sum greater than or equal to $3$ .

sugubatz