Uniform Cookie Bag Distribution

Khong Auntie is organizing a contest with x contestants. She plans to prepare x cookie bags, one for each contestant. There are k different types of cookies, numbered from 0 to k-1. A cookie of type i (0 ≤ i ≤ k-1) has a tastiness value of \(2^i\). In her storage, she has a[i] cookies of type i (possibly 0).

For each cookie type, Khong Auntie may put any nonnegative number of cookies (possibly 0) into each bag. However, the total number of cookies of type i used across all bags cannot exceed a[i]. The total tastiness of a bag is defined as the sum of the tastiness values of all cookies in that bag. Khong Auntie wants to fill the x bags so that every bag has the same total tastiness value \(y\).

Your task is to determine how many different values of \(y\) are possible under these conditions.

Problem Function

// You need to implement the function
// int64 count_tastiness(int64 x, int64[] a)
// where
//   x: the number of cookie bags to prepare
//   a: an array of length k, where for each 0 ≤ i ≤ k-1, a[i] is the number of cookies of type i available in storage
// The function should return the number of distinct \(y\) values for which it is possible to distribute the cookies so that each of the x bags has total tastiness exactly \(y\).
// Note that the function will be called for q independent scenarios.

inputFormat

The first line contains a single integer q denoting the number of test cases.

Each test case consists of two lines.

• The first line contains two integers: x and k.
• The second line contains k space-separated integers: a[0], a[1], ..., a[k-1].

It is guaranteed that each test case is independent.

outputFormat

For each test case, output a single integer on a new line — the number of distinct tastiness values \(y\) for which it is possible to prepare x cookie bags, each having total tastiness exactly \(y\).

sample

3
1 2
2 1
2 2
4 2
3 3
3 6 3

5
5
10