Chef has been in the culinary business for a long time now and with this experience, he wants to expand his profile to a professional food critic. He has been tasting various food items from different cuisines, grading them points and posting them on his blog. The blog is thriving and is gaining a lot of followers who want to take Chef’s recommendation and try out the dishes on their own.

Chef wants to create a paid program to help his readers taste the dishes but he is busy updating his blog so he wants your help.

You are given N dishes, each with base price A and score B. The cost of each food item is the ending digit of A^B. Yes, the dishes are cheap, the chef is a real people’s man!

You have to answer Q queries. Each query has a starting index L and an ending index R. In each query you have to determine the total cost of the dishes from L to R (inclusive).

INPUT :

• The first line of each test case contains N, the number of dishes
• N lines follow which contain two space-separated integers A and B, the base price and the score, respectively.
• The next line contains Q, the number of queries.
• Q lines follow which contain two space-separated integers L and R, the starting and ending indices, respectively.

OUTPUT :

                For each query print the total cost of the dishes from L to R (inclusive) in a new line.

CONSTRAINTS :

• 1 <= N <= 10⁵
• 0 <= A <= 10⁹
• 1 <= B <= 10¹⁰
• 1 <= Q <=10⁵
• 1 <= L <= R <= N