Bucket is planning to make a very long journey across the countryside by bus. Her journey consists of bus routes, numbered from 1 to in the order she must take them. The buses themselves are very fast, but do not run often. The -th bus route only runs every days.
More specifically, she can only take the -th bus on day , , and so on. Since the buses are very fast, she can take multiple buses on the same day.
Bucket must finish her journey by day , but she would like to start the journey as late as possible. What is the latest day she could take the first bus, and still finish her journey by day ?
It is guaranteed that it is possible for Bucket to finish her journey by day .
输入格式
The first line of the input gives the number of test cases, . test cases follow. Each test case begins with a line containing the two integers and . Then, another line follows containing integers, the -th one is .
输出格式
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the latest day she could take the first bus, and still finish her journey by day .
样例
样例输入 1
3
3 10
3 7 2
4 100
11 10 5 50
1 1
1
样例输出 1
Case #1: 6
Case #2: 99
Case #3: 1
数据范围与提示
In Sample Case #1, there are bus routes and Bucket must arrive by day . She could:
Take the 1st bus on day (),
Take the 2nd bus on day () and
Take the 3rd bus on day ().
In Sample Case #2, there are bus routes and Bucket must arrive by day . She could:
Take the 1st bus on day (),
Take the 2nd bus on day (),
Take the 3rd bus on day () and
Take the 4th bus on day (),
In Sample Case #3, there is bus route and Bucket must arrive by day . She could:
Take the 1st bus on day ().
Limits
.
.
.
It is guaranteed that it is possible for Bucket to finish her journey by day .
