eolymp
bolt
Try our new interface for solving problems
Problems

Mountain Holidays

Mountain Holidays

Time limit 1 second
Memory limit 64 MiB

Some time ago, Chef discovered that more and more people have started climbing mountains every day. So he decided to build restaurant in the Ukrainian resort Bukovel (Carpathian Mountains). But there are many places to choose, so he wants to choose the best one. Let us learn how attractiveness for a location is calculated.

Next to every place, is some mountain. A Mountain is a sequence of points (0, height_0), (1, height_1), ..., (n-1, height_{n-1}). where every two adjacent points are connected with a segment. For example, consider the mountain

(0, 0) (1, 2) (2, 1) (3, 2) (4, 1) (5, 3) (6, 0) (7, 1) (8, 0)

Visitors may start their climbing from some position i and finish in position j, where (i < j). They calculate the attractiveness of a mountain, as the number of different climbs that it offers. Of course, so does our Chef! A climb from position i to position j is the sequence (i, height_i), ..., (j, height_j).

Two climbs, say i_1 to j_1 and i_2 to j_2, are different if and only if (j_1– i_1)(j_2– i_2) or (height_{i1+k} – height_{i1+k-1})(height_{i2+k} – height_{i2+k–1}) for at least some k in the range [1..i_1-j_1].

Let us consider two climbs from the mountain we considered above

and

The first one is the climb from (0 to 3), and the second one is the climb from (4 to 6). They are different because (3-0)(6-4). On the other hand, climbs such as (0 to 1) and (4 to 5) are the same.

Given the array, heights, find the number of different climbs that exist on the mountain which is described by the sequence of these heights. Because answer can be very large, output it modulo 1000000009.

Input data

First line of input contains Т – the number of test cases (1T1000). The first line of each test case contains N – the number of peaks (1N100000).

On second line of each test case, there are N numbers. The ith number denotes the height of ith peak (|Height_i|10^6, |Height_i-Height_{i-1}|100).

Output data

For each test case, output a single number, the number of unique climbs.

Examples

Input example #1
3
6
1 2 3 4 5 6
9
0 2 1 2 1 3 0 1 0
7
0 5 -5 5 -5 4 -4
Output example #1
5
31
20
Author Kozhukhivskiy Vitaliy
Source Distance Summer Computer School - Summer 2013