Counting Cafeteria Menus

The company cafeteria can cook $M$ different dishes, numbered 1 through $M$.

At every meal the cafeteria puts out $N$ of those dishes, and each employee eats one of them. The dishes served at a meal are decided by this rule.

If dish $K$ was served at the previous meal, dish $K+1$ is served at this meal. If dish $M$ was served at the previous meal, dish 1 is served at this meal.

So every served number moves up by one from one meal to the next, and the number after $M$ wraps back to 1. Meals go on forever, so every menu you can reach by shifting this meal's menu again and again is served sooner or later.

Younghee just joined the company and wants to know how many different menus the cafeteria serves. She tells you the dish numbers served at this meal. Count the different menus. Two menus are the same when they hold exactly the same dish numbers.

The first line contains the number of test cases $T$. ($1 \le T \le 20$)

The first line of each test case contains $M$, the number of dishes the cafeteria can cook, and $N$, the number of dishes served at one meal. ($1 \le N \le M \le 10^6$)

Each of the next $N$ lines contains one dish number $x_i$ served at this meal. ($1 \le x_i \le M$) The numbers are distinct and sorted in increasing order.

The sum of $M$ over all test cases is at most $10^6$.

For each test case, print the number of different menus on its own line.