Description

小科比很爱玩数学。

老师让TA把一堆正整数中的素数挑出来，TA轻松搞定；

老师又让TA把这些素数的各位数字平方和一下，TA也轻松搞定；

可是老师其实是要TA将素数先化成某个n进制数，然后再各位数字平方和一下的。于是小科比不辞辛苦，化了好大功夫终于完成了这项工作；

老师一看，又说还是没有达到要求，还应该要将平方和的结果化回n进制数去。这下小科比可有点吃力了，啃哧啃哧了半天，到现在还没有做好。

好姐姐好哥哥，你快点帮帮TA吧，不然小科比的面子实在下不去。

Input

一些正整数N(1<N<100000)和n进制(1<n<17)的数对。

Output

对于每个数对N，n，虑过非素数，将素数化成n进制数，计算其各位数字平方和，再还原成n进制数，以一行的形式输出。

Sample

Input

3 2 
12 10
11 5

Output

10
10

Hint

1. 16进制数的数字若为10,11,12,13,14,15，在输出格式中分别表示为A,B,C,D,E,F。15进制数则会用到A,B,C,D,E。余类推。
2. 3的2进制数为11，其平方和为1^2+1^2=2，2的2进制数为10。
3. 11的5进制数为21，其平方和为2^2+1^2=5，5的5进制数为10。

Source: qn