TrickGCD

Problem Description

You are given an array $A$ , and Zhu wants to know there are how many different array $B$ satisfy the following conditions?

• $1\leq B_{i} \leq A_{i}$
• For each pair( l , r ) ($1 \leq l \leq r \leq n$) , $gcd( b_{l} , b_{l+1} ... b_{r} )\ge 2$

Input

The first line is an integer T($1 \leq T \leq 10$) describe the number of test cases. Each test case begins with an integer number n describe the size of array $A$. Then a line contains $n$ numbers describe each element of $A$ You can assume that $1 \leq n , A_{i} \leq 10^5$

Output

For the $k$th test case , first output "Case #k: " , then output an integer as answer in a single line . because the answer may be large , so you are only need to output answer $mod$ $10^9+7$

Sample Input

1

4

4 4 4 4

Sample Output

Case #1: 17

Source

2017 Multi-University Training Contest - Team 2

https://acm.hdu.edu.cn/showproblem.php?pid=6053