【题目描述】

以b为基数的正整数n的平方和数字函数SSD(b，n)通过表示以b为底的n来定义，如下所示：

表示数字的平方和。

编写一个程序来计算输入正数的平方和数字函数。

【输入】

第一行输入一个十进制整数P，(1≤P≤1000），表示有P组测试数据。每组数据都应以相同的方式独立处理。

每组数据由一行输入组成。它包含数据集编号K，后跟基数b（3≤b≤16），作为十进制整数，后跟正整数n（作为十进制整数），将根据基数b计算平方和数字函数。n将适合32位无符号整数。数据集编号K从1开始，每个数据集递增1。

【输出】

对于每个数据集，都有一行输出。

单行输出由数据集编号K组成，后跟一个空格，后跟SSD（b，n）的值（十进制整数）。

【样本输入1】

3

1 10 1234

2 3 98765

3 16 987654321

【样本输出1】

1 30

2 19

3 696

【样例说明】

第一行，基数b为 10 ，n为1234 所以SSD(10,1234)=1*1+2*2+3*3+4*4=30

第二行，基数b为3，n为98765，将n转换为3进制为12000110222，所以SSD(3,98765)=1*1+2*2+0*0+0*0+0*0+1*1+1*1+0*0+2*2+2*2+2*2=19

第三行，基数b为16，n为987654321，将n转换为16进制为3ADE68B1，所以SSD(3,98765)=3*3+10*10+13*13+14*14+6*6+8*8+11*11+1*1=696