After he has learned how to play Nim game, Bob begins to try another stone game which seems much easier.
The game goes like this: one player starts the game with
piles of stones. There is
stones on the ith
pile. On one turn, the player can move exactly one stone from one pile to another pile. After one turn, if there exits a number
such that for each pile
is the multiple of
is the number of stone of the this pile now), the game will stop. Now you need to help Bob to calculate the minimum turns he need to stop this boring game. You can regard that
is the multiple of any positive number.
The first line is the number of test cases. For each test case, the first line contains one positive number
indicating the number of piles of stones.
The second line contains
positive number, the
indicating the number of stones of the
The sum of N
of all test cases is not exceed
For each test case, output a integer donating the answer as described above. If there exist a satisfied number
initially, you just need to output
It's guaranteed that there exists at least one solution.
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
void del(ll n)