Hard Divide and Conquer > Dynamic Programming

![enter image description here][1] **CarryCount(x,y)** is the **sum** of carry value while adding two non-negative number x and y. <br> For example, **CarryCount**(99,1) is 2 (above picture) and **CarryCount**(100,9) is 0. You will be given Three integers **N, X and K**. You have to find the number of elements from **1 to N** such that **Carrycount(i,X)** is **exactly** **K** , where **1<=i<=N.** Input: ------ Input starts with an integer **T (1<=9720)**, denoting the number of test cases.<br> Each case contains three integer **N (1 ≤ N ≤ 10^18), X (1 ≤ X ≤ 10^18, K (0<=K<=17)** as explained above. Output: ------- For each case of input, output the result.See the samples for exact formatting. Sample Input ------------ 1 10 1 1 Sample Output ------------- Case 1: 1 [1]: https://s3-ap-southeast-1.amazonaws.com/devskillimagestorage/questionimages/6c0bff55-6520-c9d1-a94d-08d4b4b965bc_d9ee8746254f4b43a501251c4df6b851_W267xH164.png

Bir Bahadur Khatri