SP18917 DUKKAR - Dukkar and Pikka

Pika 和 Dukkar 是室友。Pika 是一个书呆子，喜欢玩数学！Pika 最喜欢的主题是帕斯卡三角形，他声称自己可以解决任何与此相关的问题。所以 Dukkar 决定验证一下这是否属实！ Dukkar 给出一个数字 $N$ 和一个质数 $P$。$N$ 是帕斯卡三角形的第 $N$ 行，从 $0$ 开始计数。Dukkar 要求 Pika 找出第 $N$ 行中有多少个数字能被 $P$ 整除。由于数字可能非常大，所以 Pika 必须编写一个程序。由于期末考试即将到来，Pika 必须在班级中名列前茅，所以他请求你的帮助。你能帮助 Pika 吗？ 

第一个包含一个整数 $T$（$T

每行一个测试结果，表示帕斯卡三角的第 $N$ 行有几个能被 $P$ 整除的数。