C. gcd hard version
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

给定两个长度为 $$$n$$$ 的数组 $$$a$$$， $$$a$$$ 数组的第 $$$i$$$ 个数 为 $$$a_i$$$, $$$b$$$ 数组的第 $$$i$$$ 个数 为 $$$b_i$$$ ， 定义$$$Gcd(l ,r)$$$ 为 $$$a$$$ 数组中下标 在$$$[l, r]$$$中的所有数的最大公因数， $$$Sum(l, r)$$$ 为 在 $$$b$$$ 数组中下标在$$$[l, r]$$$中的所有数的和。

你要找到满足 $$$Gcd(l, r) \le Sum(l, r)$$$ 的所有区间个数，即有多少种满足条件的 $$$[l, r]$$$。

$$$n \le 10^5,~1 \le a_i,~b_i \le 10^9$$$。

Input

第一行一个数字 $$$n$$$ ，表示 $$$a$$$, $$$b$$$ 两个数组的长度

第二行 $$$n$$$ 个数，第 $$$i$$$ 个数表示 $$$a_i$$$

第三行 $$$n$$$ 个数，第 $$$i$$$ 个数表示 $$$b_i$$$

Output

一个数字表示满足条件的区间个数。

Example
Input
3
2 2 2
1 2 1
Output
4