Repovive

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/2/problems/C

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/2/problems/C

Repovive

Rayan discovered $n$ ancient runes arranged in a row. Each rune has a power level $a_i$ .

A contiguous segment $[l, r]$ is called harmonious if its bitwise AND divides its length:

(a_l \land a_{l+1} \land \ldots \land a_r) \mid (r - l + 1)

Count the total number of harmonious segments.

Note: $0$ does not divide any positive integer.

Input

The first line contains the number of test cases $t$ ( $1 \le t \le 2 \times 10^5$ ).

For each test case:

The first line contains $n$ ( $1 \le n \le 2 \times 10^5$ ), the number of runes.
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $0 \le a_i \le 10^9$ ).

The sum of $n$ over all test cases does not exceed $2 \times 10^5$ .

Output

For each test case, print the number of harmonious segments.

t \\[0.5em] \left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

\begin{array}{l} cnt_1 \\ cnt_2 \\ \vdots \\ cnt_t \end{array}

2C. Divisible Segments

Input

Output

Input

Output

Samples

Input

Output