Contents
Chef and Deque solution codechef

For Solution
Click Here!
Chef and one of his friends were practicing for ICPC together by giving each other programming problems.
In Chef’s turn, Chef gave his friend a modified deque (doubleended queue), initially with NN elements A1,A2,…,ANA1,A2,…,AN, which supported performing operations of the following type: Chef and Deque solution codechef
 Choose an integer KK, which must be a power of 22 (possibly 20=120=1). Additionally, each particular value of KK can only be chosen if it has not been chosen in any previous operation.
 Delete KK elements from the end of the deque.
 Then, you may also decide to delete KK elements from the beginning of the deque.
 However, the deque is not allowed to become completely empty.
Chef also gave his friend a special integer MM and asked him to find the minimum number of operations needed such that the sum of the elements remaining in the deque is divisible by MM, or determine that it is impossible to achieve this goal.
Chef’s friend could not solve the problem and asked for your help. Can you solve it for him?
Input Format Chef and Deque solution codechef
 The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
 The first line of each test case contains two spaceseparated integers NN and MM.
 The second line contains NN spaceseparated integers A1,A2,…,ANA1,A2,…,AN.
Output Format
For each test case, print a single line containing one integer — the minimum number of required operations or −1−1 if it is impossible to achieve the goal.
Constraints Chef and Deque solution codechef
 1≤T≤1001≤T≤100
 1≤N≤2⋅1051≤N≤2⋅105
 1≤M≤1091≤M≤109
 1≤Ai≤1091≤Ai≤109 for each valid ii
 the sum of NN over all test cases does not exceed 3⋅1053⋅105
Subtasks
Subtask #1 (15 points):
 N≤2,000N≤2,000
 the sum of NN over all test cases does not exceed 5,0005,000
Subtask #2 (20 points): if it is possible to achieve the goal, at most 44 operations are needed
Subtask #3 (65 points): original constraints
Sample Input 1 Chef and Deque solution codechef
4
4 7
8 6 4 6
7 13
10 2 3 8 1 10 4
7 1
7 3 7 2 9 8 10
3 11
3 4 8
Sample Output 1
1
2
0
1
Explanation Chef and Deque solution codechef
Example case 1: The only possible way is to keep the first two elements 88 and 66, since 8+6=148+6=14, which is divisible by 77. Hence we must delete 22 elements from the end in 11 operation.
Example case 3: The sum of all elements is already divisible by 11.
Example case 4: It is impossible to achieve the goal.