给你一个正整数（记为 $N$）和一个在该整数中的位置（记为 $P$），要求对 $N$ 做一次变换。变换规则如下：从右往左数，找到 $N$ 的第 $P$ 位数字。

• 把该位左边的每一位数字替换为：该数字与第 $P$ 位数字之和。
• 把该位右边的每一位数字替换为：该数字与第 $P$ 位数字之差的绝对值。
• 把第 $P$ 位数字替换为：$N$ 的不同素因子个数。注意：$1$ 不是素数，它没有素因子。一个素数恰好有 $1$ 个素因子（就是它本身）。

输入格式

共有 $5$ 组数据。每组包含两个正整数 $N$ 和 $P$。其中 $N < 10^{15}$，并且 $P$ 一定是合法的位置。

输出格式

输出每组输入对应的变换后结果。输出的数字中间不能有空格。

样例

输入

102438 3
4329 1
6710 2
16807 1
60098065452 7

输出

546414
1312113
7841
8131571
1488173823436