该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem Background

Muxue the youth has collected many number cards and discovered that some number cards are particularly lucky—the sum of their digits is a prime number. To test his memory, he has designed a game.

Problem Description

Muxue has n number cards, each card has a number aᵢ. Muxue considers a number lucky if the sum of its digits is a prime number.

Now Muxue will perform q operations, each operation is one of two types:

1. Increase the number on the x-th card by y.
2. Query how many lucky numbers are in the interval [l, r].

Please help Muxue efficiently complete these operations.

Input Format

First line: two integers n, q (1 ≤ n, q ≤ 10^5)
Second line: n integers a₁, a₂, ..., aₙ (1 ≤ aᵢ ≤ 10^6)
Next q lines: each line contains an operation

• 1 x y: Increase aₓ by y (1 ≤ x ≤ n, 1 ≤ y ≤ 100)
• 2 l r: Query the number of lucky numbers in interval [l, r] (1 ≤ l ≤ r ≤ n)

Output Format

For each type 2 operation, output an integer representing the answer.

Sample Input and Output

Input

5 3
13 25 7 42 19
2 1 5
1 3 3
2 1 5

Output

2
1

Explanation/Notes

Explanation for the sample: Initial: 13(1+3=4 not prime), 25(7 prime), 7(7 prime), 42(6 not prime), 19(10 not prime), total 2 lucky numbers. Increase the 3rd card 7 by 3 to get 10(1+0=1 not prime). Query: 13, 25, 10, 42, 19, total 1 lucky numbers.

Note: Numbers may exceed 10^6, but the sum of their digits will not exceed 54 (6×9).

This problem uses Subtask bundled testing