Last night, Nitu came across the following pseudo-code. She understood that this method would take two integer values and a list of integers as input. She decided to implement this method in her preferred programming language and tried calling it with various sets of values. However, she encountered performance issues with her implementation for certain input values, as it did not execute within the expected timeframe. Can you assist her in implementing this pseudo-code?
1FUNCTION CountLuckyNumbers(l, r, forbidden_list) 2 # Initialize a counter for lucky numbers 3 count_lucky_numbers = 0 4 5 # Loop through the range from l to r (inclusive) 6 FOR i FROM l TO r 7 # Convert the current number to a string 8 current_number = CONVERT_TO_STRING(i) 9 10 # Initialize a flag to determine if the number is allowed 11 is_allowed = TRUE 12 13 # Check if the current number contains any of the forbidden numbers 14 FOR EACH forbidden IN forbidden_list 15 # Convert the forbidden number to a string for comparison 16 forbidden_string = CONVERT_TO_STRING(forbidden) 17 18 # If the current number contains the forbidden number as a substring, 19 # Set the flag to false and exit the loop 20 IF current_number CONTAINS forbidden_string 21 is_allowed = FALSE 22 BREAK 23 END IF 24 END FOR 25 26 # If the current number is allowed, increment the lucky number count 27 IF is_allowed 28 INCREMENT count_lucky_numbers BY 1 29 END IF 30 END FOR 31 32 # Return the count of lucky numbers 33 RETURN count_lucky_numbers 34END FUNCTION
The input begins with an integer, indicating the number of test cases.
For each test case:
The first line contains an integer, which represents the size of the forbidden list.
The subsequent lines contain integers, each representing an element in the forbidden list. Each of these elements falls within the range to .
Finally, there is a line containing two integers, and where both and are within the range of to .
For each test case, please provide a single line of output in the following format: .
Here, represents the test case number, and represents the result returned by the pseudocode.
1 2 3 6 1 10
Case #1: 8