We all know about the classical Fibonacci series, Fibonacci series is F(n) = F(n-1) + F(n-2). For this question we call it a 2-Nacci series as a new element is calculated as the sum of the last 2 terms of the series. For Fibonacci we assume F(0)=0 and F(1)=1. We define as new series N-Nacci where F(n) is the sum of the last n terms and here we assume that F(0)=0, F(1)=1, F(2)=2 ... F(n-1) = (n-1). Your task is to calculate the last K digits of the Lth term of the N-Nacci series (no leading zeros needed).

Constraints

2 ≤ N ≤ 30

K ≤ 8

L ≤ 1000000000

Input

The first line of the input denotes the number of test cases t (at most 10). Each line denotes a test case consisting of N, K, L.

Output

For each test case print the last K digits of the Lth term of the N-Nacci series.

Example

Input:
4
2 1 5
3 6 12
4 1 10
4 2 10

Output:
5
778
6
16