朽木裂，雷霆惊，丛林木马怒冲天。 众所周知，如果给你两个数 要你计算 的值，你就知道要这么做：把每一位相乘并且乘上它们的 然后相加，其中 表示对应数位的幂次。 有一次，可怜的 ZM 不小心把“相乘”中的所有乘法运算都算成了加法，她想让你帮忙算算，这样算出来的结果是多少？

输入描述:

全文第一行输入一个整数 ，表示数据组数。每行输入两个正整数 ，表示两个因数。数据保证 ，其中 表示两个数的位数。

输出描述:

每行输出一个数表示你计算出的答案，为方便输出，你只需要输出最终结果对 取模后的值即可。