{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"prob-content\"\u003e\n \u003cp\u003e寒假又快要到了,不过对于lzx来说,头疼的事又来了,因为众多的后宫都指望着能和lzx约会呢,lzx得安排好计划才行。\u003c/p\u003e \n \u003cp\u003e假设lzx的后宫团有n个人,寒假共有m天,而每天只能跟一位后宫MM约会,并且由于后宫数量太过庞大了,而寒假的天数太少,所以lzx在寒假里不会与一个MM约会一次以上。现在lzx想要知道:寒假安排的方案数如果写成k进制,末位会有多少个0。\u003c/p\u003e \n \u003c/div\u003e\n "}},{"title":"Input","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"prob-content\"\u003e\n \u003cp\u003e输入的第一行是一个整数,为数据的组数t(t\u0026lt;\u003d1000)。\u003c/p\u003e \n \u003cp\u003e每组数据占一行,为3个正整数n、m和k(1\u0026lt;\u003dm\u0026lt;\u003dn\u0026lt;2^31,2\u0026lt;\u003dk\u0026lt;2^31),意思如上文所述。\u003c/p\u003e \n \u003c/div\u003e\n "}},{"title":"Output","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"prob-content\"\u003e\n 对于每组数据,输出一个数,为寒假安排的方案数写成k进制末位的0的数目。\n \u003c/div\u003e\n "}},{"title":"Sample Input","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"prob-content\"\u003e\n \u003cpre class\u003d\"sample\"\u003e3\r\n10 5 10\r\n10 1 2\r\n10 2 8\u003c/pre\u003e\n \u003c/div\u003e\n "}},{"title":"Sample Output","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"prob-content\"\u003e\n \u003cpre class\u003d\"sample\"\u003e1\r\n1\r\n0\u003c/pre\u003e\n \u003c/div\u003e\n "}}]}