题目描述

等差数列B+A,B+2A,…,B+NA。求所有项标准二进制表示中1的总数量。

本题为一本通1805的本地训练修订版。

输入

第一行T，1≤T≤20；每组A B N，1≤A≤10000，1≤B≤10^16，1≤N≤10^12。

输出

每组输出一行精确整数。

输入样例

2
4 7 1
5 8 2

输出样例

3
5

修订说明

保留原全部数量级与协议，明确每项标准无符号二进制和精确整数答案。

本地修订与来源

本题为经授权补全的本地训练修订版，原始公开题面保留在采集档案；修订了：保留原全部数量级与协议，明确每项标准无符号二进制和精确整数答案。。此处题意、范围和输出约定以本修订版为准，不冒称原站或官方原版。原题链接：https://ybt.ssoier.cn/problem_show.php?pid=1805。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共4个测试点，非原站或官方原始数据。总分100分。