Mystery Gift Box is an interesting item when shopping on online markets. The Huy store is also selling this item. The store has imported ~N~ items, with the ~i~-th item priced at ~A_i~.

Each mystery gift box selected by the store will consist of 3 items, such that the price difference between the most expensive item and the cheapest item among the selected items does not exceed ~d~.

Task: Help the store count the number of different ways to select a mystery gift box. Two selections are different if there is at least one item in one selection that is not present in the other selection.

Input:

• The first line contains two integers ~N~ and ~d~ (~0 ≤ d ≤ 10^6~);
• The second line contains a sequence of integers ~A_1, A_2, ..., A_N~ (~1 ≤ A_i ≤ 10^6~). The numbers are separated by spaces.

Output:

• A single integer representing the number of possible selections.

Simple Input

5 3  
6 1 7 2 4

Simple Output

2

Notes:

There are two possible selections:

• ~{1, 2, 4}~
• ~{4, 6, 7}~

Constraints

• ~60\%~ of the test cases correspond to ~1 ≤ N ≤ 200~ and ~A_i ≤ A_{i+1}~ for ~1 ≤ i < N~;
• ~20\%~ of the test cases correspond to ~1 ≤ N ≤ 10^4~;
• ~20\%~ of the test cases correspond to ~1 ≤ N ≤ 2 × 10^6~.

Given an array ~A~ of ~N~ prime numbers: ~A_1, A_2, ..., A_N~, a beautiful number is a number that is divisible by at least one prime number in the array ~A~.

Task: Given the integer ~N~ and the array ~A~, count the number of beautiful numbers that do not exceed ~M~.

Input:

• The first line contains two integers ~N~ and ~M~ (~1 ≤ N ≤ 20~);
• The second line contains the sequence of integers ~A_1, A_2, ..., A_N~. The numbers are separated by spaces.

Output:

• A single integer representing the number of beautiful numbers.

Sample Input

2 11  
3 5

Sample Output

5

Notes

• The beautiful numbers are: ~3, 5, 6, 9, 10~.

Constraints

• ~60\%~ of the test cases correspond to ~1 ≤ M ≤ 10^6~, ~1 ≤ A_i ≤ 10^5~;
• ~20\%~ of the test cases correspond to ~1 ≤ M ≤ 10^9~, ~10^5 < A_i ≤ 10^9~;
• ~20\%~ of the test cases correspond to ~1 ≤ M ≤ 10^{18}~, ~1 ≤ A_i ≤ 10^{18}~.

Hung is an excellent student in computer science and is very interested in studying numbers in mathematics. One day, after studying prime numbers in class, he realized that there are prime numbers for which the sum of the digits of their squares results in a new integer that is still a prime number. These numbers are called perfect prime numbers, and the others are called imperfect prime numbers (prime numbers whose square's digit sum is not a prime number).

When Hung returned home, he quickly opened his computer to explore these numbers. However, when he opened the computer, he suddenly found a strange sequence of ~N~ positive integers (called sequence ~A~) in a folder on his computer. Hung now wants to know how many perfect prime numbers and how many imperfect prime numbers there are in this sequence.

Task: Help Hung process this information.

Input

• The first line contains the number ~N~, which is the length of the sequence.
• The second line contains the sequence ~A~ consisting of ~N~ positive integers.

Output

• Output two integers: the count of perfect prime numbers and the count of imperfect prime numbers, separated by a space.

Sample Input

5  
9 7 11 13 5

Sample Output

2 2

Notes

• ~7~ is a perfect prime number because ~7^2 = 49~, and the sum of the digits is ~4 + 9 = 13~, which is a prime number.
• ~11~ is an imperfect prime number because ~11^2 = 121~, and the sum of the digits is ~1 + 2 + 1 = 4~, which is not a prime number.
• ~13~ is an imperfect prime number because ~13^2 = 169~, and the sum of the digits is ~1 + 6 + 9 = 16~, which is not a prime number.
• ~5~ is a perfect prime number because ~5^2 = 25~, and the sum of the digits is ~2 + 5 = 7~, which is a prime number.

Constraints

• ~50\%~ of the test cases have ~N ≤ 5 \times 10^3~ and ~A_i ≤ 10^4~.
• ~40\%~ of the test cases have ~N ≤ 5 \times 10^5~ and ~A_i ≤ 10^7~.
• ~10\%~ of the test cases have ~N ≤ 10^6~ and ~A_i ≤ 10^8~.

Jack - J97 is a boy who loves programming and is also very fond of Western architecture, as these structures are often symmetrical, with matching patterns on both the left and right sides. Jack often enjoys working on programming problems, and one day, while practicing on an online platform, he came across an interesting problem that closely matches his interests. The problem can be summarized as follows: "Given ~Q~ queries, each with two positive integers ~L~ and ~R~, the task is to count how many palindromic numbers with even lengths exist in the range ~[L, R]~. A palindromic number is a number that reads the same backward as forward." The problem is quite interesting, so J97 wanted to share it with others, and now you are tasked with solving it.

Input

• The first line contains an integer ~Q~, the number of queries.
• The following ~Q~ lines each contain two integers ~L~ and ~R~.

Output

• For each query, output the number of palindromic numbers with even lengths in the range ~[L, R]~.

Sample Input

2  
79 97  
1 100

Sample Output

1  
9

Notes

• For the range ~[79, 97]~, the only palindromic number is ~88~.
• For the range ~[1, 100]~, the palindromic numbers are: ~11, 22, 33, 44, 55, 66, 77, 88, 99~.

Constraints

• ~30\%~ of the test cases correspond to ~Q ≤ 10^2~ and ~L ≤ R ≤ 10^5~.
• ~40\%~ of the test cases correspond to ~Q ≤ 5 \times 10^3~ and ~L ≤ R ≤ 10^9~.
• ~30\%~ of the test cases correspond to ~Q ≤ 10^5~ and ~L ≤ R ≤ 10^{12}~.

Sol is studying the unique biological function of a species of plant called the Snow Tree on an unnamed planet. After many days of observation, Sol has noticed that the reproductive pattern of the Snow Tree is quite unusual. Specifically, the Snow Tree does not sprout when its seeds are sown. Instead, when certain conditions are met, it appears and exists at a fixed point according to a certain rule, with an initial height of ~a~. After some time, it grows another Snow Tree in front of it with a random height ~b~, and then continues to grow more trees based on the following rule: "The height of any Snow Tree is always the average of the height of the previous tree and the next tree."

Task: Based on the recorded heights of the first two Snow Trees, calculate the height of the ~n~-th Snow Tree.

Input

• The first line contains two integers: the heights of the first two trees ~a~ and ~b~.
• The second line contains a positive integer ~n~.

Output

• Print the height of the ~n~-th Snow Tree.

Sample Input 1

2 3  
4

Sample Output 1

5

Sample Input 2

1 2  
3

Sample Output 2

3

Constraints

• ~20\%~ of the test cases correspond to ~a, b, n ≤ 10^{18}~.
• ~60\%~ of the test cases correspond to ~a, b, n ≤ 10^{10^{4}}~.
• ~20\%~ of the test cases correspond to ~a, b, n ≤ 10^{10^{5}}~.