Maddy 来到了一座褪色的高塔面前，高塔下方的石碑上刻着一个数字 。 Maddy 发现旁边的石头上有一个机关，她按下了机关，发现石碑上的数字如下变化：
Maddy 很好奇，她按了 次机关，她记录下了原本的 以及这 次按下机关之后的得数，共 个数字 。 Maddy 希望知道上述 个得数之和对 取模的值 是多少，请帮助她求出。
第一行输入一个整数 ()，表示数据组数。 每组测试数据输入的唯一一行输入两个整数 和 () 分别表示石碑上所刻的数字和 Maddy 所按机关的次数。
每组测试数据输出一行一个整数 ，表示上述得数之和对 取模的答案。
4 1 100 2 4 74700 1 2279 1
2 6 6 5
对于第 1 组样例， 在按下机关后总还是 ，每次的得数都为 ，总和为 ，取模为 。 对于第 2 组样例，数字变化如下：，，，，这 5 个数字的和对 9 取模为 。 对于第 3 组样例，数字变化如下：。 对于第 4 组样例，数字变化如下：。
一个是 对 9 取模表示的是这个数除以 9 之后产生的余数。
