 # DCP-368: CarryCount Back to All Problems

Hard Divide and Conquer > Dynamic Programming

![enter image description here] **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 : https://s3-ap-southeast-1.amazonaws.com/devskillimagestorage/questionimages/6c0bff55-6520-c9d1-a94d-08d4b4b965bc_d9ee8746254f4b43a501251c4df6b851_W267xH164.png

### Problem Limits

 Language Time Limit (seconds) C 1.00 C++ 1.00 C++14 1.00 C# 2.00 Go 2.00 Java 2.00 JavaScript 2.00 Objective-C 2.00 Perl 2.00 PHP 2.00 Python 2.00 Python3 2.00 Ruby 2.00 VB.Net 2.00

# 12/35

Solve/Submission

### Ranking

# User Language Timing
01 Morass Cpp14 0.06s
02 flash_7 Cpp14 0.10s
03 sahedsohel Cpp 0.16s
04 Bruteforceman Cpp 0.18s
05 mamun4122 Cpp 0.27s