Extreme Escalator Pogo (Large)

Robbit Downey Hopper invented the dangerous sport of Extreme Escalator Pogo. Do not try it at home, even if you own an escalator.

Extreme Escalator Pogo needs two things: a jumping device called a pogo stick, and a fast escalator whose $N$ steps rise at a constant speed. Some steps are red and the rest are blue. Robbit starts by landing on a blue step somewhere in the middle of the escalator, on his pogo stick. From then on he keeps jumping straight up while the steps move underneath him. He may land only on blue steps. If he lands on a red step he is out, and his challenger Leepie Froggison takes her turn. Whoever makes the highest jump wins.

After touching his first blue step, Robbit always jumps to a height of 1 and lands on the very next step. That step had better be blue, or Robbit is out. On every later jump he picks one of three options:

• dampen the jump and decrease its height by 1,
• keep the height of the current jump,
• amplify the jump and increase its height by 1.

A jump of height $H$ lasts exactly as long as $H$ escalator steps need to pass underneath Robbit, so a jump of height $H$ from step $p$ lands on the step $H$ places after $p$. A jump of height zero is not allowed, and the height has no upper limit. The steps run on a loop that cycles forever, so the step after step $N$ is step 1 again.

A jump that ends on a red step is still a jump Robbit made, so its height counts as a height he reached.

Given $N$ and the colour of every step, pick the starting step and the sequence of jumps that make the greatest height Robbit reaches as large as possible.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains an integer $N$, then an integer $K$, then $K$ integers between 1 and $N$ that list the blue steps. Every step that is not listed is red. The step after step $N$ is step 1.

Limits

• $1 \le T \le 100$
• $3 \le N \le 10^9$
• $1 \le K \le \min(N, 1000)$
• The blue step numbers are distinct and given in increasing order.

For each test case, print one line of the form "Case #$x$: $H$", where $x$ is the test case number starting from 1 and $H$ is the greatest height Robbit can reach. If there is no limit on the height, print "infinity" in place of $H$.

In the first case of the first example, the best Robbit can do is start on step 2, jump to height 1 and land on step 3, then jump to height 2 and land on the red step 1. The greatest height reached this way is 2.

In the second case, the best plan starts on step 5 and lands on step 6 with height 1, step 8 with height 2, step 1 with height 3, step 5 with height 4, and step 10 with height 5. Step 10 is red, so the run ends there and the answer is 5.

In the third case, Robbit starts on step 1 and keeps jumping forever, so he reaches any height he wants.