题目描述

作为商人，比尔非常喜欢金币。一天，当他一遍遍数着自己的金币时，一个女巫走进了他的屋子。女巫告诉他，她可以把他的 n 个硬币换成 n^m。当然，比尔知道如果 m 大于 1，数字增长的速度有多快。所以他感到很高兴。但是，有一个前提条件是，比尔在获得硬币之前必须回答女巫一个关于女巫的问题。比尔可以用 t(1 ≤ t ≤ n) 个袋子来存放 n^m 个硬币，并且每个袋子里的硬币数量应该相等，女巫提的问题是有多少种方式来存储硬币。比尔很失望，因为他无法解决它，但他也不想放弃。所以他需要你的帮助，说不定你解决之后会分享金币。

输入格式

每个测试用例包含两个数字 n(1 ≤ n ≤ 10^8) 和 m(1 ≤ m ≤ 10)，处理到文件末尾。

输出格式

对于每种情况，在一行中打印存储方式的数量。

6 2
1 3
2 9

5
1
2