寒假安排

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

寒假又快要到了,不过对于lzx来说,头疼的事又来了,因为众多的后宫都指望着能和lzx约会呢,lzx得安排好计划才行。

假设lzx的后宫团有n个人,寒假共有m天,而每天只能跟一位后宫MM约会,并且由于后宫数量太过庞大了,而寒假的天数太少,所以lzx在寒假里不会与一个MM约会一次以上。现在lzx想要知道:寒假安排的方案数如果写成k进制,末位会有多少个0。

Input

输入的第一行是一个整数,为数据的组数t(t<=1000)。

每组数据占一行,为3个正整数n、m和k(1<=m<=n<2^31,2<=k<2^31),意思如上文所述。

Output

对于每组数据,输出一个数,为寒假安排的方案数写成k进制末位的0的数目。

Sample Input

3
10 5 10
10 1 2
10 2 8

Sample Output

1
1
0

Source

Dshawn

Manager

Information
Solved Number186
Submit Number821
Problem Tags
math
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel