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≤Bi≤Ai
- For each pair( l , r ) (1≤l≤r≤n) , gcd(bl,bl+1...br)≥2
Input
The first line is an integer T(1≤T≤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≤n,Ai≤105
Output
For the kth 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 109+7
Sample Input
1
4
4 4 4 4
Sample Output
Case #1: 17
