SHIVAM SHUKLA'S BLOG (OCTROME): May 2020

Like any unknown mathematician, Yuri has favourite numbers: $A$

B

C

, and

D

, where

A \leq B \leq C \leq D

. Yuri also likes triangles and once he thought: how many non-degenerate triangles with integer sides

x

y

, and

z

exist, such that

A \leq x \leq B \leq y \leq C \leq z \leq D

holds?

Yuri is preparing problems for a new contest now, so he is very busy. That's why he asked you to calculate the number of triangles with described property.

The triangle is called non-degenerate if and only if its vertices are not collinear.

Input

The first line contains four integers: $A$

B

C

and

D

(

1 \leq A \leq B \leq C \leq D \leq 5 \cdot 10^{5}

) — Yuri's favourite numbers.

Output

Print the number of non-degenerate triangles with integer sides $x$

y

, and

z

such that the inequality

A \leq x \leq B \leq y \leq C \leq z \leq D

holds.

Examples

Input

Copy

1 2 3 4

Output

Copy

Input

Copy

1 2 2 5

Output

Copy

Input

Copy

500000 500000 500000 500000

Output

Copy

Note

In the first example Yuri can make up triangles with sides $(1, 3, 3)$

(2, 2, 3)

(2, 3, 3)

and

(2, 3, 4)

In the second example Yuri can make up triangles with sides $(1, 2, 2)$

(2, 2, 2)

and

(2, 2, 3)

In the third example Yuri can make up only one equilateral triangle with sides equal to $5 \cdot 10^{5}$

Solution in Python :

l = [int(i) for i in input().split()]

length = len(l)
count = 0
for a in range(l[0] , l[1]+1) :
    for b in range(l[1],l[2]+1) :
        for c in range(l[2] ,l[3]+1) :
                 if a+b > c and b+c > a and c+a > b :
                    count += 1
print(count)

Let's define the following recurrence:

a n + 1 = a n + m i n D i g i t (a n) \cdot m a x D i g i t (a n) .

Here $m i n D i g i t (x)$

and

m a x D i g i t (x)

are the minimal and maximal digits in the decimal representation of

x

without leading zeroes. For examples refer to notes.

Your task is calculate $a_{K}$

for given

a_{1}

and

K

Input

The first line contains one integer $t$

(

1 \leq t \leq 1000

) — the number of independent test cases.

Each test case consists of a single line containing two integers $a_{1}$

and

K

(

1 \leq a_{1} \leq 10^{18}

1 \leq K \leq 10^{16}

) separated by a space.

Output

For each test case print one integer $a_{K}$

on a separate line.

Example

Input

Copy

Output

Copy

Note

$a_{1} = 487$

$a_{2} = a_{1} + m i n D i g i t (a_{1}) \cdot m a x D i g i t (a_{1}) = 487 + min (4, 8, 7) \cdot max (4, 8, 7) = 487 + 4 \cdot 8 = 519$

$a_{3} = a_{2} + m i n D i g i t (a_{2}) \cdot m a x D i g i t (a_{2}) = 519 + min (5, 1, 9) \cdot max (5, 1, 9) = 519 + 1 \cdot 9 = 528$

$a_{4} = a_{3} + m i n D i g i t (a_{3}) \cdot m a x D i g i t (a_{3}) = 528 + min (5, 2, 8) \cdot max (5, 2, 8) = 528 + 2 \cdot 8 = 544$

$a_{5} = a_{4} + m i n D i g i t (a_{4}) \cdot m a x D i g i t (a_{4}) = 544 + min (5, 4, 4) \cdot max (5, 4, 4) = 544 + 4 \cdot 5 = 564$

$a_{6} = a_{5} + m i n D i g i t (a_{5}) \cdot m a x D i g i t (a_{5}) = 564 + min (5, 6, 4) \cdot max (5, 6, 4) = 564 + 4 \cdot 6 = 588$

$a_{7} = a_{6} + m i n D i g i t (a_{6}) \cdot m a x D i g i t (a_{6}) = 588 + min (5, 8, 8) \cdot max (5, 8, 8) = 588 + 5 \cdot 8 = 628$

$a_{7} = a_{6} + m i n D i g i t (a_{6}) \cdot m a x D i g i t (a_{6}) = 588 + min (5, 8, 8) \cdot max (5, 8, 8) = 588 + 5 \cdot 8 = 628$

$a_{7} = a_{6} + m i n D i g i t (a_{6}) \cdot m a x D i g i t (a_{6}) = 588 + min (5, 8, 8) \cdot max (5, 8, 8) = 588 + 5 \cdot 8 = 628$

Sunday, 17 May 2020

Codeforces Round #643 (Div. 2) : C. Count Triangles : Solution in python

Saturday, 16 May 2020

Codeforces Round #643 (Div. 2) : Sequence with Digits : Solution in python

Blog Archive

Stats