Limits 1s, 512 MB

Clever girl Meena likes to climb trees. One day her brother Raju, after coming back from school, said to Meena with joyful eyes, “I have seen a big tree with many ripe mangoes. Let's go climb that one!”.

We can think of the mango tree as a connected undirected graph with no cycles and having exactly one path from one node to another. Meena asked Raju to describe the tree. Raju could not memorize the exact structure of the tree but remembered how many nodes were at each level considering the tree is rooted. Suddenly, they both got worried as many trees could satisfy that condition and Meena could not climb trees with all diameters.

In tree data structures, the root node is said to be at level 0, the root node's children are at level 1, and the children of that node at level 1 will be at level 2, and so on. And, the diameter of a tree means the number of nodes on the longest path in the tree.

Can you help Meena and Raju determine how many unique diameter lengths are possible for any such tree?

Suppose that, the mango tree has nn levels. For each level i (0i<n)i\ (0 \leq i < n) there exists a[i]a[i] nodes, 00-indexed.
You will be given an array bb of length m (m<n)m\ (m < n), 11-indexed.
Now, to construct aa from b,b, you need to follow the following instructions:

  • a[0]=1a[0] = 1

  • a[i]=b[i]a[i] = b[i] for 1im1 \leq i \leq m

  • a[i]=a[im]a[i]=a[i-m] for m<i<nm < i < n


The first line will contain T (1T105),T\ (1 \leq T \leq 10^5), the number of test cases.
For each test cases, the first line will contain two integers n, m (2n109, 1m<min(n,105)),n,\ m\ (2 \leq n \leq 10^9,\ 1 \leq m < min(n,10^5)), the number of levels in the tree and the length of the array b.b.
In the next line, there will be mm integers denoting the elements of array b (1b[j]109,for all 1jm).b\ ( 1 \leq b[j] \leq 10^9, for\ all\ 1 \leq j \leq m ).

It’s guaranteed that,

m\sum m over all test cases 2×105.\leq 2 × 10^5.


For each test case, output a single integer denoting the possible number of unique diameter lengths.


3 1


Login to submit.


64% Solution Ratio
monna4335Earliest, 2w ago
dlwlrm4Fastest, 0.0s
user.8953Lightest, 5.1 MB
monna4335Shortest, 650B
Toph uses cookies. By continuing you agree to our Cookie Policy.