Digit Removal solution codechef

You are given an integer NN and a digit DD. Find the minimum integer you should add to NN such that the final value of NN does not contain the digit DD.

Input Format Digit Removal solution codechef

• The first line contains TT denoting the number of test cases. Then the test cases follow.
• Each test case contains two integers NN and DD on a single line denoting the original number and the digit you need to avoid.

Output Format Digit Removal solution codechef

For each test case, output on a single line the minimum integer you should add to NN.

Constraints Digit Removal solution codechef

• 1T1051≤T≤105
• 1N1091≤N≤109
• 0D90≤D≤9

• Subtask 1 (100 points): Original constraints

Sample Input 1

5
21 5
8 8
100 0
5925 9
434356 3


Sample Output 1  Digit Removal solution codechef

0
1
11
75
5644


Explanation Digit Removal solution codechef

Test case 11: N=21N=21 does not contain the digit D=5D=5. Hence there is no need to add any integers to NN.

Test case 22: If 11 is added to N=8N=8, it becomes equal to 99, which does not contain the digit D=8D=8.

Test case 33: The minimum integer you should add to N=100N=100 such that the final value of NN does not contain the digit D=0D=0 is 1111.

Test case 55: The minimum integer which is greater than 434356434356 and does not contain the digit D=3D=3 is 440000440000. So we should add 440000434356=5644440000−434356=5644.

Digit Removal solution codechef

Chef has met up with his old friend Jack recently. Jack told Chef that he found a recipe for an ancient dish, but unfortunately, it is locked in a safe and to open the safe, it is necessary to enter the solution to the following problem.

There is a sequence of non-negative integers A1,A2,,ANA1,A2,…,AN on the safe. Find the number of pairs (l,r)(l,r) (1lrN1≤l≤r≤N) which satisfy the condition

(AlAl+1Ar)(AlAl+1Ar)max(Al,Al+1,,Ar).(Al∨Al+1∨…∨Ar)⊕(Al∧Al+1∧…∧Ar)≥max(Al,Al+1,…,Ar).

Here,  denotes bitwise XOR,  denotes bitwise OR and  denotes bitwise AND.

Jack and Chef cannot think of anything except the recipe, so you are asked to open the safe.

Input Digit Removal solution codechef

• The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
• The first line of each test case contains a single integer NN.Digit Removal solution codechef
• The second line contains NN space-separated integers A1,A2,,ANA1,A2,…,AN.

Output Digit Removal solution codechef

For each test case, print a single line containing one integer ― the number of pairs (l,r)(l,r) that satisfy the given condition.

Constraints Digit Removal solution codechef

• 1N1061≤N≤106
• 0Ai<2600≤Ai<260 for each valid ii
• the sum of NN over all test cases does not exceed 106106

Subtask #1 (10 points): for each valid iiAiAi is a power of 22

Subtask #2 (30 points): Digit Removal solution codechef

• Ai3105Ai≤3⋅105 for each valid ii
• the sum of NN over all test cases does not exceed 31053⋅105

Subtask #3 (60 points): original constraints

Sample Input 1  Digit Removal solution codechef

2
4
0 1 2 3
6
1 3 5 6 4 2


Sample Output 1  Digit Removal solution codechef

6
11


Explanation Digit Removal solution codechef

Example case 1: The pairs (l,r)(l,r) satisfying the condition are (1,1)(1,1)(1,2)(1,2)(1,3)(1,3)(1,4)(1,4)(2,3)(2,3) and (2,4)(2,4).