Luhn's Algorithm Problem Statement We need check credit card numbers, and find out if they are valid credit card number or not. Credit card numbers use an algorithm called "Luhn's algorithm". Luhn's algorithm uses something called a $$check digit$,$ which is the last digit in the credit card number. The credit card number must pass the following test: $1.$ Find the check digit $($the rightmost digit$)$ Using the example number $4539682995824395,$ the check digit is $52.$ From the check digit, move left and, double the value of every second digit. Using the example number $4539682995824395,$ every second number would be: $9,4,8,9,2,6,3,4$ If we double one of these numbers and the result is greater than $9($e$.$g$.,92=18),$ then add the digits of the product $($e$.$g$.,18$: $1+8=7,16$: $1+6=7)$ Note: The same result can be found by subtracting $9$ from the product $($e$.$g$.,16$: $16-9=7,18$: $18-9=9)).3.$ Take the sum of all the digits from step $2,$ including the ones we didn$$t double. $8+5+6+9+3+8+4+9+9+5+7+2+8+3+9+54.$ Get modulo $10$ of the result from step $3.$ If the answer is $0$ then the number is valid according to the Luhn Algorithm. Try writing out the algorithm with pen and paper before you start writing code. Input Format An n$-$digit credit card number, where the last digit is the check digit. Output Format Output "VALID" if it is a valid credit card number and "INVALID" if it is not. Constraints $4<=$n$<=30$ Sample Input $4539682995824395$ Sample Output VALID Explanation Make sure to read from right to left. First, add the numbers that we won$$t double: $45396829958243955+3+2+5+9+8+9+5=46$ Now, double every second digit from the second last digit and subtract $9$ if needed. $45396829958243952*9=18$; $18-9=92*4=82*8=16$; $16-9=72*9=18$; $18-9=92*2=42*6=12$; $12-9=32*3=62*4=89+8+7+9+4+3+6+8=54$ Adding these together $46+54=100100\%10==0$ So the card is VALID