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$
输入解释
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$
输出解释
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$