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$