package main

import (
	"bufio"
	"fmt"
	"os"
)

const MAXA = 1000000

var (
	a         []int
	min_val   []int
	max_val   []int
	cnt_case3 [MAXA + 1]int
	cnt_case4 [MAXA + 1]int
	ans       int64

	div_head [MAXA + 2]int
	div_list []int
)

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func init() {
	for i := 1; i <= MAXA; i++ {
		for j := i; j <= MAXA; j += i {
			div_head[j+1]++
		}
	}
	for i := 1; i <= MAXA+1; i++ {
		div_head[i] += div_head[i-1]
	}
	div_list = make([]int, div_head[MAXA+1])

	var cur_head [MAXA + 2]int
	copy(cur_head[:], div_head[:])

	for i := 1; i <= MAXA; i++ {
		for j := i; j <= MAXA; j += i {
			div_list[cur_head[j]] = i
			cur_head[j]++
		}
	}
}

func readInt(reader *bufio.Reader) int {
	var res int
	b, err := reader.ReadByte()
	if err != nil {
		return 0
	}
	for b < '0' || b > '9' {
		b, err = reader.ReadByte()
		if err != nil {
			return 0
		}
	}
	for b >= '0' && b <= '9' {
		res = res*10 + int(b-'0')
		b, err = reader.ReadByte()
		if err != nil {
			break
		}
	}
	return res
}

func solve(L, R int) {
	if L == R {
		if a[L]%a[L] == 0 {
			ans++
		}
		return
	}
	mid := (L + R) / 2
	solve(L, mid)
	solve(mid+1, R)

	min_val[mid] = a[mid]
	max_val[mid] = a[mid]
	for i := mid - 1; i >= L; i-- {
		min_val[i] = min(min_val[i+1], a[i])
		max_val[i] = max(max_val[i+1], a[i])
	}

	min_val[mid+1] = a[mid+1]
	max_val[mid+1] = a[mid+1]
	for i := mid + 2; i <= R; i++ {
		min_val[i] = min(min_val[i-1], a[i])
		max_val[i] = max(max_val[i-1], a[i])
	}

	for i := L; i <= mid; i++ {
		if max_val[i]%min_val[i] == 0 {
			low, high := mid+1, R
			p1 := R + 1
			for low <= high {
				m := (low + high) / 2
				if min_val[m] < min_val[i] {
					p1 = m
					high = m - 1
				} else {
					low = m + 1
				}
			}

			low, high = mid+1, R
			p2 := R + 1
			for low <= high {
				m := (low + high) / 2
				if max_val[m] > max_val[i] {
					p2 = m
					high = m - 1
				} else {
					low = m + 1
				}
			}

			valid := min(p1, p2) - (mid + 1)
			if valid > 0 {
				ans += int64(valid)
			}
		}
	}

	for j := mid + 1; j <= R; j++ {
		if max_val[j]%min_val[j] == 0 {
			low, high := L, mid
			q1 := mid + 1
			for low <= high {
				m := (low + high) / 2
				if min_val[m] > min_val[j] {
					q1 = m
					high = m - 1
				} else {
					low = m + 1
				}
			}

			low, high = L, mid
			q2 := mid + 1
			for low <= high {
				m := (low + high) / 2
				if max_val[m] < max_val[j] {
					q2 = m
					high = m - 1
				} else {
					low = m + 1
				}
			}

			valid := mid - max(q1, q2) + 1
			if valid > 0 {
				ans += int64(valid)
			}
		}
	}

	curr_p1 := mid + 1
	curr_p2 := mid + 1
	for i := mid; i >= L; i-- {
		for curr_p2 <= R && min_val[curr_p2] >= min_val[i] {
			if curr_p2 >= curr_p1 {
				v := max_val[curr_p2]
				start := div_head[v]
				end := div_head[v+1]
				for k := start; k < end; k++ {
					cnt_case3[div_list[k]]++
				}
			}
			curr_p2++
		}
		for curr_p1 <= R && max_val[curr_p1] <= max_val[i] {
			if curr_p1 < curr_p2 {
				v := max_val[curr_p1]
				start := div_head[v]
				end := div_head[v+1]
				for k := start; k < end; k++ {
					cnt_case3[div_list[k]]--
				}
			}
			curr_p1++
		}
		if curr_p1 < curr_p2 {
			ans += int64(cnt_case3[min_val[i]])
		}
	}
	for j := curr_p1; j < curr_p2; j++ {
		v := max_val[j]
		start := div_head[v]
		end := div_head[v+1]
		for k := start; k < end; k++ {
			cnt_case3[div_list[k]]--
		}
	}

	curr_p1 = mid + 1
	curr_p2 = mid + 1
	for i := mid; i >= L; i-- {
		for curr_p2 <= R && max_val[curr_p2] <= max_val[i] {
			if curr_p2 >= curr_p1 {
				cnt_case4[min_val[curr_p2]]++
			}
			curr_p2++
		}
		for curr_p1 <= R && min_val[curr_p1] >= min_val[i] {
			if curr_p1 < curr_p2 {
				cnt_case4[min_val[curr_p1]]--
			}
			curr_p1++
		}
		if curr_p1 < curr_p2 {
			v := max_val[i]
			start := div_head[v]
			end := div_head[v+1]
			for k := start; k < end; k++ {
				ans += int64(cnt_case4[div_list[k]])
			}
		}
	}
	for j := curr_p1; j < curr_p2; j++ {
		cnt_case4[min_val[j]]--
	}
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	a = make([]int, 500005)
	min_val = make([]int, 500005)
	max_val = make([]int, 500005)

	t := readInt(reader)
	for tc := 0; tc < t; tc++ {
		n := readInt(reader)
		for i := 0; i < n; i++ {
			a[i] = readInt(reader)
		}
		ans = 0
		solve(0, n-1)
		fmt.Fprintln(writer, ans)
	}
}