문제
x명이 참가하는 대회를 주관하고 있는 안티 콩은 각 참가자들에게 비스킷 가방을 하나씩 나눠주려 한다.
서로 다른 k가지 종류의 비스킷에는 0부터 k - 1까지 번호가 붙어 있다.
0 ≤ i ≤ k - 1인 i에 대해, i번 비스킷은 맛 점수가 2i이고, 안티 콩은 창고에 i번 비스킷을 ai개 갖고 있다.(ai는 0일 수 있다.)
안티 콩은 각 비스킷 가방에 모든 종류의 비스킷을 0개 이상씩 담으려고 한다.
모든 가방에 담긴 i번 비스킷의 개수의 합은 ai개를 넘을 수 없다.
한 가방에 담긴 모든 비스킷의 맛 점수의 합을 그 가방의 총 맛이라고 한다.
각 가방의 총 맛이 y가 되도록 x개의 비스킷 가방을 만들 수 있는 서로 다른 y값이 얼마나 많은지 안티 콩이 찾을 수 있도록 도와라.
입력
1번 줄 : q
이후 다음과 같은 쿼리가 q회 주어진다.
1번 줄 : k x
2번 줄 : a0 a1 ... ak-1
1 ≤ k ≤ 60
1 ≤ q ≤ 1 000
1 ≤ x ≤ 1018
0 ≤ ai ≤ 1018 (0 ≤ i ≤ k - 1)
각 쿼리에 대하여, 창고에 있는 모든 비스킷의 맛 점수의 합은 1018을 넘지 않는다.
출력
각 줄에 i번째 쿼리에 대하여 각 가방의 총 맛이 y가 되도록 안티 콩이 x개의 비스킷 가방을 쌀 수 있는 서로 다른 y값의 개수를 출력하여라.
예제1
입력
2
33
521
32
212
출력
5
6
힌트
출처
IOI 2020 day2 1