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}$。