数数

【题目描述】

ztxz16从小立志成为码农，因此一直对数的二进制表示很感兴趣。今天的数学课上，ztxz16学习了等差数列的相关知识。我们知道，一个等差数列可以用三个数$A,B,N$表示成如下形式： $B + A, B + 2×A, B + 3×A, ..., B + N×A$ ztxz16想知道对于一个给定的等差数列，把其中每一项用二进制表示后，一共有多少位是$1$。

【输入】

第一行输入一个整数$T$表示数据组数； 接下来$T$行每行输入三个整数$A,B,N$。

【输出】

输出$T$行，每行一个整数表示答案。

【输入样例】

2
4 7 1
5 8 2

【输出样例】

3
5

【提示】

【数据规模】 对于30%的数据：$1≤T≤20 , 1≤A≤10000 , 1≤B≤10^{16} , 1≤N≤10^3$。 对于60%的数据：$1≤T≤20 , 1≤A≤10000 , 1≤B≤10^{16} , 1≤N≤10^9$。 对于100%的数据：$1≤T≤20 , 1≤A≤10000 , 1≤B≤10^{16} , 1≤N≤10^{12}$。