题目描述

在计算机上处理一些大数据相乘时，由于计算机硬件的限制，不能直接进行相乘得到想要的结果。

可以将一个大的整数乘法分而治之，将大问题变成小问题，变成简单的小数乘法再进行合并，从而解决上述问题。 






分解：

首先将2个大整数a(n位）、b(m位)分解为两部分：ah和al、bh和bl

ah表示大整数a的高位，al表示大整数a的低位，，ah、al为n/2位。

bh表示大整数b的高位，bl表示大整数b的低位，，bh、bl为m/2位。

2个大整数a(n位)、b(m位）相乘转换成了4个乘法运算ahbh、ahbl、albh、albl，而乘数的位数变为了原来的一半。

求解子问题：

继续分解两个乘法运算，直到分解有一个乘数位1位数时停止分解，进行乘法运算并记录结果。

合并：

将计算出的结果相加并回溯，求出最终结果。

为了降低难度现给你两个位数相同且位数均为2的幂的正整数x和y，你需要打印他们每次分治的结果，并在最后打印x*y。

输入格式

第一行一个正整数 T (0

接下来1~T+1行 每行两个正整数 x，y (0

输出格式

对于每组x y打印他们每次分治的结果并在最后打印x*y。

2
1 2
1124 1233

2

1124 * 1233 =( 11 * 10 ^ 2 + 24 ) * ( 12 * 10 ^ 2 + 33 ) = 11 * 12 * 10 ^ 4 + ( 11 * 33 + 24 * 12 ) * 10 ^ 2 + 24 * 33
11 * 12 =( 1 * 10 ^ 1 + 1 ) * ( 1 * 10 ^ 1 + 2 ) = 1 * 1 * 10 ^ 2 + ( 1 * 2 + 1 * 1 ) * 10 ^ 1 + 1 * 2
11 * 33 =( 1 * 10 ^ 1 + 1 ) * ( 3 * 10 ^ 1 + 3 ) = 1 * 3 * 10 ^ 2 + ( 1 * 3 + 1 * 3 ) * 10 ^ 1 + 1 * 3
24 * 12 =( 2 * 10 ^ 1 + 4 ) * ( 1 * 10 ^ 1 + 2 ) = 2 * 1 * 10 ^ 2 + ( 2 * 2 + 4 * 1 ) * 10 ^ 1 + 4 * 2
24 * 33 =( 2 * 10 ^ 1 + 4 ) * ( 3 * 10 ^ 1 + 3 ) = 2 * 3 * 10 ^ 2 + ( 2 * 3 + 4 * 3 ) * 10 ^ 1 + 4 * 3
1385892