七段数码管（seven segment display）是一种用于显示十进制数字的电子显示设备，是比复杂的点阵显示器更简单的替代方案。七段数码管广泛应用于数字时钟、电子仪表、简易计算器以及其他显示数字信息的电子设备中。

Marjar 大学的学生 Edward 本学期正在学习“逻辑与计算机设计基础”课程。为了完成课程项目，他购买了一个八位七段数码管组件，用来制作一个十六进制计数器。

为了显示一个十六进制数，七段数码管组件需要消耗一定的电能。显示一个十六进制数的总能耗是该数每一位数字显示能耗的总和。Edward 在互联网上找到了下表，其中描述了显示每种数字的能耗。

例如，要在组件上显示十六进制数 “5A8BEF67” 一秒钟，将消耗 $5 + 6 + 7 + 5 + 5 + 4 + 6 + 3 = 41$ 单位的能量。

Edward 的十六进制计数器工作方式如下： 计数器仅工作 $n$ 秒。$n$ 秒后，计数器停止显示。 在第 1 秒开始时，计数器开始显示预先配置好的八位十六进制数 $m$。 * 在第 $i$ 秒结束时（$1 \le i < n$），显示的数字将增加 1。如果增加后的数字大于十六进制数 “FFFFFFFF”，计数器会将数字重置为 0 并继续显示。

给定 $n$ 和 $m$，Edward 对七段数码管组件消耗的总能量感兴趣。你能帮他解决这个问题吗？

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试数据的组数。对于每组测试数据： 第一行包含一个整数 $n$ ($1 \le n \le 10^9$) 和一个大写的八位十六进制数 $m$ ($00000000 \le m \le FFFFFFFF$)，其含义如上所述。

我们温馨提示，本题包含大量的输入输出，建议使用较快的 I/O 方法。例如，在 C++ 中可以使用 scanf/printf 代替 cin/cout。

输出格式

对于每组测试数据，输出一行，表示八位七段数码管组件消耗的总能量单位。

样例

输入 1

3
5 89ABCDEF
3 FFFFFFFF
7 00000000

输出 1

208
124
327

说明

对于第一组测试数据，计数器在 5 秒内将显示 5 个十六进制数（89ABCDEF, 89ABCDF0, 89ABCDF1, 89ABCDF2, 89ABCDF3）。总能耗为： $(7 + 6 + 6 + 5 + 4 + 5 + 4 + 6) +$ $(7 + 6 + 6 + 5 + 4 + 5 + 4 + 2) +$ $(7 + 6 + 6 + 5 + 4 + 5 + 4 + 5) +$ $(7 + 6 + 6 + 5 + 4 + 5 + 4 + 5) = 208$

对于第二组测试数据，计数器在 3 秒内将显示 3 个十六进制数（FFFFFFFF, 00000000, 00000001）。总能耗为： $(4 + 4 + 4 + 4 + 4 + 4 + 4 + 4) +$ $(6 + 6 + 6 + 6 + 6 + 6 + 6 + 6) +$ $(6 + 6 + 6 + 6 + 6 + 6 + 6 + 2) = 124$