1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <stdio.h>
short ranks[10]={0},arr[8][5000000]={0};
int p;
 
 
void init()
{
     int i,j=1;
     for(i=1;i<500501;i++)
     {
                        if(i==(j*(j+1))/2)
                        {
                            arr[0][i]=j;
                            j++;
                        }
                        else
                            arr[0][i]=arr[0][i-1];
     }
     j=1;
     for(i=1;i<1001001;i++)
     {
                        if(i==(j*(j+1)))
                        {
                            arr[1][i]=j;
                            j++;
                        }
                        else
                            arr[1][i]=arr[1][i-1];
     }
     j=1;
     for(i=1;i<1501501;i++)
     {
                        if(i==3*(j*(j+1))/2)
                        {
                            arr[2][i]=j;
                            j++;
                        }
                        else
                            arr[2][i]=arr[2][i-1];
     }
     j=1;
     for(i=1;i<2002001;i++)
     {
                        if(i==2*(j*(j+1)))
                        {
                            arr[3][i]=j;
                            j++;
                        }
                        else
                            arr[3][i]=arr[3][i-1];
     }
     j=1;
     for(i=1;i<2502501;i++)
     {
                        if(i==5*(j*(j+1))/2)
                        {
                            arr[4][i]=j;
                            j++;
                        }
                        else
                            arr[4][i]=arr[4][i-1];
     }
     j=1;
     for(i=1;i<3003001;i++)
     {
                        if(i==3*(j*(j+1)))
                        {
                            arr[5][i]=j;
                            j++;
                        }
                        else
                            arr[5][i]=arr[5][i-1];
     }
     j=1;
     for(i=1;i<3503501;i++)
     {
                        if(i==7*(j*(j+1))/2)
                        {
                            arr[6][i]=j;
                            j++;
                        }
                        else
                            arr[6][i]=arr[6][i-1];
     }
     j=1;
     for(i=1;i<4004001;i++)
     {
                        if(i==4*(j*(j+1)))
                        {
                            arr[7][i]=j;
                            j++;
                        }
                        else
                            arr[7][i]=arr[7][i-1];
     }   
}
 
 
int b_search(int lower, int upper)
{
    int mid = (lower+upper)/2,i,sum,x,time;
    for(;lower<=upper;mid=(lower+upper)/2)
    {
                        sum=0;
                        for(i=1;i<9;i++)
                        {
                                        if(ranks[i]!=0)
                                        {
                                                      x=ranks[i]*arr[i][mid];
                                                      sum+=x;
                                        }
                        }
                        if(sum>=p)
                        {
                                  time=mid;
                                  upper=mid-1;
                        }
                        else
                                  lower=mid+1;
    }
}                                                            
 
int main()
{
    int t,l,i,j,time,r;
    init();
    scanf("%d%*c",&t);
    while(t--)
    {
              scanf("%d %d",&p,&l);
              for(i=0;i<l;i++)
              {
                              scanf("%d",&r);
                              ranks[r]++;
              }
              for(i=1;i<9;i++)
              {
                              if(ranks[i]!=0)
                              {
                                            j=i-1;
                                            break;
                              }
              }
              for(i=1;i<4004001;i++)
              {
                                    if(p==arr[j][i])
                                        break;
              }
              time = b_search(1,arr[j][i]);
              printf("%d\n",time);
    }
    return 0;
}
              
 

I2luY2x1ZGUgPHN0ZGlvLmg+CnNob3J0IHJhbmtzWzEwXT17MH0sYXJyWzhdWzUwMDAwMDBdPXswfTsKaW50IHA7CgoKdm9pZCBpbml0KCkKewogICAgIGludCBpLGo9MTsKICAgICBmb3IoaT0xO2k8NTAwNTAxO2krKykKICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIGlmKGk9PShqKihqKzEpKS8yKQogICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBhcnJbMF1baV09ajsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGorKzsKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBhcnJbMF1baV09YXJyWzBdW2ktMV07CiAgICAgfQogICAgIGo9MTsKICAgICBmb3IoaT0xO2k8MTAwMTAwMTtpKyspCiAgICAgewogICAgICAgICAgICAgICAgICAgICAgICBpZihpPT0oaiooaisxKSkpCiAgICAgICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGFyclsxXVtpXT1qOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgaisrOwogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGFyclsxXVtpXT1hcnJbMV1baS0xXTsKICAgICB9CiAgICAgaj0xOwogICAgIGZvcihpPTE7aTwxNTAxNTAxO2krKykKICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIGlmKGk9PTMqKGoqKGorMSkpLzIpCiAgICAgICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGFyclsyXVtpXT1qOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgaisrOwogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGFyclsyXVtpXT1hcnJbMl1baS0xXTsKICAgICB9CiAgICAgaj0xOwogICAgIGZvcihpPTE7aTwyMDAyMDAxO2krKykKICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIGlmKGk9PTIqKGoqKGorMSkpKQogICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBhcnJbM11baV09ajsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGorKzsKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBhcnJbM11baV09YXJyWzNdW2ktMV07CiAgICAgfQogICAgIGo9MTsKICAgICBmb3IoaT0xO2k8MjUwMjUwMTtpKyspCiAgICAgewogICAgICAgICAgICAgICAgICAgICAgICBpZihpPT01KihqKihqKzEpKS8yKQogICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBhcnJbNF1baV09ajsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGorKzsKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBhcnJbNF1baV09YXJyWzRdW2ktMV07CiAgICAgfQogICAgIGo9MTsKICAgICBmb3IoaT0xO2k8MzAwMzAwMTtpKyspCiAgICAgewogICAgICAgICAgICAgICAgICAgICAgICBpZihpPT0zKihqKihqKzEpKSkKICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgYXJyWzVdW2ldPWo7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBqKys7CiAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgICAgICAgICAgYXJyWzVdW2ldPWFycls1XVtpLTFdOwogICAgIH0KICAgICBqPTE7CiAgICAgZm9yKGk9MTtpPDM1MDM1MDE7aSsrKQogICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgaWYoaT09NyooaiooaisxKSkvMikKICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgYXJyWzZdW2ldPWo7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBqKys7CiAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgICAgICAgICAgYXJyWzZdW2ldPWFycls2XVtpLTFdOwogICAgIH0KICAgICBqPTE7CiAgICAgZm9yKGk9MTtpPDQwMDQwMDE7aSsrKQogICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgaWYoaT09NCooaiooaisxKSkpCiAgICAgICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGFycls3XVtpXT1qOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgaisrOwogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGFycls3XVtpXT1hcnJbN11baS0xXTsKICAgICB9ICAgCn0KCgppbnQgYl9zZWFyY2goaW50IGxvd2VyLCBpbnQgdXBwZXIpCnsKICAgIGludCBtaWQgPSAobG93ZXIrdXBwZXIpLzIsaSxzdW0seCx0aW1lOwogICAgZm9yKDtsb3dlcjw9dXBwZXI7bWlkPShsb3dlcit1cHBlcikvMikKICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgc3VtPTA7CiAgICAgICAgICAgICAgICAgICAgICAgIGZvcihpPTE7aTw5O2krKykKICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaWYocmFua3NbaV0hPTApCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHg9cmFua3NbaV0qYXJyW2ldW21pZF07CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHN1bSs9eDsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgICAgICBpZihzdW0+PXApCiAgICAgICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHRpbWU9bWlkOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgdXBwZXI9bWlkLTE7CiAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbG93ZXI9bWlkKzE7CiAgICB9Cn0gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAKCmludCBtYWluKCkKewogICAgaW50IHQsbCxpLGosdGltZSxyOwogICAgaW5pdCgpOwogICAgc2NhbmYoIiVkJSpjIiwmdCk7CiAgICB3aGlsZSh0LS0pCiAgICB7CiAgICAgICAgICAgICAgc2NhbmYoIiVkICVkIiwmcCwmbCk7CiAgICAgICAgICAgICAgZm9yKGk9MDtpPGw7aSsrKQogICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgc2NhbmYoIiVkIiwmcik7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHJhbmtzW3JdKys7CiAgICAgICAgICAgICAgfQogICAgICAgICAgICAgIGZvcihpPTE7aTw5O2krKykKICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGlmKHJhbmtzW2ldIT0wKQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaj1pLTE7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgZm9yKGk9MTtpPDQwMDQwMDE7aSsrKQogICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaWYocD09YXJyW2pdW2ldKQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICAgfQogICAgICAgICAgICAgIHRpbWUgPSBiX3NlYXJjaCgxLGFycltqXVtpXSk7CiAgICAgICAgICAgICAgcHJpbnRmKCIlZFxuIix0aW1lKTsKICAgIH0KICAgIHJldHVybiAwOwp9CiAgICAgICAgICAgICAgCg==